84. Largest Rectangle in Histogram

题目

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 <= 105
• 0 <= heights[i] <= 104

Related Topics

栈

数组

单调栈

👍 2948

👎 0

思路

1、单调栈中按照栈底->栈顶 递增顺序存储当前元素的索引

如果遇到下一个元素比栈顶元素小时，因为计算面积按照最小值计算，此时最大元素的优势在后续节点的优势已经不再，故此时进行计算

推导过程如下

i = 0, h = 2 → stack = [0]
i = 1, h = 1 → 1 < 2 ⇒ pop 0 ⇒ area = 2 × 1 = 2 → stack = [1]
i = 2, h = 5 → stack = [1,2]
i = 3, h = 6 → stack = [1,2,3]
i = 4, h = 2 → 2 < 6 ⇒ pop 3 ⇒ area = 6 × 1 = 6
             → 2 < 5 ⇒ pop 2 ⇒ area = 5 × 2 = 10 (✅ max so far)
             → stack = [1,4]
i = 5, h = 3 → stack = [1,4,5]
i = 6, h = 0 → pop 5 ⇒ area = 3 × 1 = 3
             → pop 4 ⇒ area = 2 × 4 = 8
             → pop 1 ⇒ area = 1 × 6 = 6

所有栈顶元素出栈，并计算当前面积

• 最小高度：栈顶元素索引的高度
• 最小宽度：
  • 右边界：i
  • 左边界：栈顶元素的前一个元素代表着目标矩形的左边界(被包含)，如存在，stack[-1] +1
  • 宽度 = i or i - stack[-1] - 1

2、如何去计算最后一个元素的值呢？

将单调栈中注入一个虚拟节点，高度为0 即可完成最后整个已知矩形的出栈

解法

# leetcode submit region begin(Prohibit modification and deletion)
class Solution:
    def largestRectangleArea(self, heights: List[int]) -> int:
        heights.append(0)
        res = 0
        stack = []
        for i in range(len(heights)):
            while stack and heights[i] < heights[stack[-1]]:
                height = heights[stack.pop()]
                width = i if not stack else i - stack[-1] - 1
                res = max(res, width * height)
            stack.append(i)
        return res
        
# leetcode submit region end(Prohibit modification and deletion)

复杂度分析

• 时间复杂度 O(N)
• 空间复杂度 O(N)