尘雨尘风

数学与编程的爱好者

0%

leetcode题解84：柱状图中最大的矩形

发表于 分类于
本文字数： 1.1k 阅读时长 ≈ 1 分钟

描述

该题来自于力扣第84题

分析

首先看看暴力的方法怎么做，对于每个高度h，当然是包含这个高度的范围即宽越大，面积越大，所以从看该高度左边和右边第一个小于h的在哪里，就确定了宽是多少。比如说[2,1,5,6,2,3]中，看包含高度5的最大宽是所少？从5向左遍历，1是第一个小于5的；从5向右看，2是第一个小于5的，所以包含5的最大范围是[5,6]，宽度为2，从而面积为10。所以暴力做法就是，对所有高度找到其最大宽，然后计算出包含该高度的最大面积，最终求出全局的最大面积就是结果。

从暴力的做法来看，其根本就是找出在左边和右边的第一个小于当前值的位置。都学过数据结构单调栈，但是好像不知道单调栈的具体用处，该题就是其用处之一。先用上面的例子看看单调栈都做了什么。

  1. 首先2入栈，栈内元素[2]
  2. 这是待入栈元素1比栈顶元素2小，从而2出栈，1再入栈，栈内元素[1]
  3. 5比栈顶元素1大，直接入栈，栈内元素[1,5]
  4. 6比栈顶元素5大，直接入栈，栈内元素[1,5,6]
  5. 2比栈顶元素6小，6出栈，栈内元素[1,5]
  6. 2比栈顶元素5小，5出栈，栈内元素[1]
  7. 2比栈顶元素1大，直接入栈，栈内元素[1,2]
  8. 3比栈顶元素2大，直接入栈，栈内元素[1,2,3]
  9. 无元素继续入栈，直接栈顶元素3出栈，栈内元素[1,2]
  10. 2出栈，然后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 = []
        heights.append(-1)
        max_ = 0
        for i in range(len(heights)):
            while len(stack) > 0 and heights[stack[-1]] > heights[i]:
                j = stack.pop()
                if len(stack) == 0:
                    w = i
                else:
                    w = i - stack[-1] - 1
                max_ = max(max_, w * heights[j])

            stack.append(i)
        return max_
相关文章