LeetCode84 柱状图中最大的矩形

发表于 | 分类于 |
字数统计: 696 | 阅读时长 ≈ 2

链接: https://leetcode-cn.com/problems/largest-rectangle-in-histogram/

题意

给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为1 。
求在该柱状图中，能够勾勒出来的矩形的最大面积。

解法

可以把这个问题想象成锯木板，如果木板都是递增的那我很开心，如果突然遇到一块木板$i$矮了一截，那我就先找之前最戳出来的一块（其实就是第$i-1$块），计算一下这个木板单独的面积，然后把它锯成次高的，这是因为我之后的计算都再也用不着这块木板本身的高度了。再然后如果发觉次高的仍然比现在这个i木板高，那我继续单独计算这个次高木板的面积（应该是第$i-1$和$i-2$块），再把它俩锯短。直到发觉不需要锯就比第$i$块矮了，那我继续开开心心往右找更高的。为了避免到了最后一直都是递增的，所以可以在最后加一块高度为0的木板。

由于需要在数组中每一个找到第一个比自己小的数，考虑使用单调栈。
基础模型其实就是：在一维数组中对每一个数找到第一个比自己小的元素。这类“在一维数组中找第一个满足某种条件的数”的场景就是典型的单调栈应用场景。

单调栈满足如下性质：

  • 当元素出栈时，说明这个新元素是出栈元素向后找第一个比其小的元素。
  • 当元素出栈后，说明新栈顶元素是出栈元素向前找第一个比其小的元素。
    例如当前栈为[1, 5, 6]，新元素为2
  1. 首先将6出栈，说明2是6向后找的第一个比其小的数
  2. 出栈后，栈顶元素为5，说明5是6向前找第一个比其小的数

在出栈的过程中完成面积的计算，得到最大面积值
为了防止栈空以及序列递增的情况，在队首和队尾添加一个0作为”哨兵节点”

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        if (heights.empty()) return 0;
        vector<int> stk;
        heights.insert(heights.begin(), 0);
        heights.push_back(0);
        int ans = 0, n = heights.size();
        for (int i = 0; i < n; i++) {
            while(stk.size() && heights[stk.back()] > heights[i]){
                int cur = stk.back();
                stk.pop_back();
                int r = i - 1, l = stk.back() + 1; 
                // stk.back()是比已出栈数小的第一个数，所以stk.back() + 1 对应的数比当前栈顶大
                ans = max(ans, heights[cur] * (r - l + 1));
            }
            stk.push_back(i);
        }
        return ans;
    }
};