LeetCode Problem 84-Largest Rectangle in Histogram

柱状图中最大的矩形。给定 n 个非负整数,用来表示柱状图中各个柱子的高度。每个柱子彼此相邻,且宽度为 1 。

求在该柱状图中,能够勾勒出来的矩形的最大面积。

以上是柱状图的示例,其中每个柱子的宽度为 1,给定的高度为 [2,1,5,6,2,3]

图中阴影部分为所能勾勒出的最大矩形面积,其面积为 10 个单位。

示例:

1
2
输入: [2,1,5,6,2,3]
输出: 10

思路一

使用堆栈,堆栈中存储柱子高度的下标。首先我们思考一个问题,假设使用遍历的方法,应该怎样计算当前柱子高度所对应的最大面积,如下所示:

1
2
3
4
5
6
7
8
         6
      5  6
      5  6
      5  6     3
2     5  6  2  3
2  1  5  6  2  3
----------------
0  1 (2) 3  4  5

假设现在需要知道第 2 个柱子对应的最大面积,则需要从此柱子向左遍历找到第一个高度比其小的柱子的下标,即 1,以及向右遍历找到第一个高度比其小的柱子的下标,即 4,则第 2 个柱子高度对应的最大面积就为 。即如果使用遍历的方法,需要找到每个柱子对应的左右界,然后更新最大面积。

如果能有方法自动保存每个柱子高度的左界,则只需要知道柱子的右界即可算出该柱子高度对应的最大面积,使用堆栈保存柱子的下标,当当前柱子的高度比栈顶柱子的高度大时,柱子下标入栈,相反,当当前柱子的高度比栈顶柱子高度小时,即此时已经找到栈顶柱子的右界,而栈顶柱子的左界即栈中第二个元素,此时就可以计算栈顶柱子高度对应的最大面积,如下所示:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
      6 
   5  6
   5  6
   5  6     3
   5  6  2  3
1  5  6  2  3
----------------
1  2 (3) 4  5
===================
假设此时栈中元素为[1,2,3],遇到第 right=4 个柱子,
因为第 right 个柱子高度比 heights[stack[-1]] 小,栈顶元素出栈,记为 idx,
出栈后的栈顶元素即为高度为 heights[idx] 的柱子的左界,
而第 right 个元素则为 heights[idx]的右界,
所以计算 heights[idx] 对应的面积为 heights[idx] * (right - stack[-1] - 1)
而此时的 right 还需要与新的栈顶元素进行比较,所以 right -= 1
====================
需要注意的是第一个元素和最后一个元素,
在栈中先存入-1方便第一个元素面积的计算,
遇到最后一个元素的时候也需要栈顶元素出栈。

代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
    def largestRectangleArea(self, heights: List[int]) -> int:
        stack, right = [-1], 0
        rs = 0
        while right <= len(heights):
            # 当栈为空时或者满足高度条件时,入栈
            if stack[-1] == -1 or (right < len(heights) and heights[right] >= heights[stack[-1]]):
                stack.append(right)
            # 当遇到最后一个元素时或者不满足高度条件时,出栈
            elif right == len(heights) or heights[right] < heights[stack[-1]]:
                idx = stack.pop()
                left = stack[-1]
                rs = max(rs, heights[idx] * (right - left - 1))
                right -= 1  # 继续考虑当前元素
            right += 1
        return rs

时间复杂度

思路二

换一种写法。

1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def largestRectangleArea(self, heights: List[int]) -> int:
        heights.append(0)
        stack, rs = [-1], 0
        for i in range(len(heights)):
            while stack and heights[stack[-1]] > heights[i]:
                h = heights[stack.pop()]
                w = i - stack[-1] - 1
                rs = max(rs, h * w)
            stack.append(i)
        return rs

相似问题

  1. Maximal Rectangle
此时不赞何时赞!