LeetCode 084 Largest Rectangle in Histogram

LeetCode

<div>

Given an array of integers heights representing the histogram's bar height where the width of each bar is 1, return the area of the largest rectangle in the histogram.

Example 1:

<pre>Input: heights = [2,1,5,6,2,3] Output: 10 Explanation: The above is a histogram where width of each bar is 1. The largest rectangle is shown in the red area, which has an area = 10 units. </pre>

Example 2:

<pre>Input: heights = [2,4] Output: 4 </pre>

Constraints:

• 1 <= heights.length <= 10<sup>5</sup>
• 0 <= heights[i] <= 10<sup>4</sup>

</div>

题目大意：

求直方图中最大的矩形面积

解题思路：

类似于L042 Trapping Rain Water的stack法，但此题水量是反的。所以仍然用Stack，但用递增栈

解题步骤：

N/A

注意事项：

1. 比L042稍简单，不用处理最后一个bar高度和宽度计算，但是用递增栈且公式中宽度计算仍然采用i - stack[-1] - 1，因为bar并不一定连续，如212, 最后一个2入栈，栈中剩下[_, 1]第一个2已经出栈了，但是可以有水量的。
2. 原数组头尾加入0，头0是因为公式有stack[-1]避免越界， 尾0是因为让所有留在栈中的bar出栈且计算。

大厦题，首尾加入节点：
LeetCode 084 Largest Rectangle in Histogram LeetCode 218 The Skyline Problem

Python代码：

def largestRectangleArea(self, heights: List[int]) -> int:
	stack, res = [], 0
	heights.insert(0, 0) # remember
	heights.append(0)
	for i in range(len(heights)):
		while stack and heights[i] < heights[stack[-1]]:
			index = stack.pop()
			res = max(res, (i - stack[-1] - 1) * heights[index]) # remember i - stack[-1] - 1 not i - index
		stack.append(i)
	return res

算法分析：

时间复杂度为O(n)，空间复杂度O(n)