LeetCode 084 Largest Rectangle in Histogram

LeetCode

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:

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.

Example 2:

Input: heights = [2,4]
Output: 4

Constraints:

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

题目大意：

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

解题思路：

类似于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)