2022秋招备战！每天写至少一篇Leetcode里Hard难度题目的题解

84. 柱状图中最大的矩形

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

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

示例 1:

输入：heights = [2,1,5,6,2,3]
输出：10
解释：最大的矩形为图中红色区域，面积为 10

示例 2：

输入： heights = [2,4]
输出： 4

提示：

• 1 <= heights.length <=105
• 0 <= heights[i] <= 104

单调栈的典中典题目。

思路：利用单调栈的特性，对于每个高度，我们要找到第一个比他小的左边的高度和右边的高度，利用两者的下标之差来计算宽度。最后用宽度乘以高度取最大值即可。

我们可以从左到右侧进行遍历，利用维护一个所有元素连续不下降的单调栈。这样，当我们遇到一个比栈顶要低的高度后，就可以pop出栈内所有高于该高度的下标，并且这个下标的值的右侧第一个比他小的高度的坐标，就是我们当前的坐标。

如何找到每个高度左侧，第一个高度比当前高度小的坐标？从右往前遍历即可。

朴素做法可以将2次遍历的结果保存在数组里。

一个小细节。可以将保存左侧数组的初始值初始化为-1，右侧数组的初始值初始化为n作为哨兵。当一个元素左侧或者右侧没有比他小的时候，用-1和n进行计算，就不用分类讨论了。假设有个高度下标为3， 高度为1，左侧和右侧都没有比他小的高度。那么他的宽度是n - (- 1) - 1。计算方式和没有用到哨兵值的高度一样。

朴素好理解一些的的代码

class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        stack<int> s;
        int res = 0;
        int n = heights.size();
        vector<int> left (n, -1);
        vector<int> right(n, n);
        for (int i = 0; i < n; i++) {
            while (!s.empty() && heights[s.top()] > heights[i]) {
                right[s.top()] = i;
                s.pop();
            }
            s.push(i);
        }
        while (!s.empty()) s.pop();
        for (int i = n - 1; i >= 0; i--) {
            while (!s.empty() && heights[s.top()] > heights[i]) {
                left[s.top()] = i;
                s.pop();
            }
            s.push(i);
        }

        for (int i = 0; i < n; i++) {
            int width = right[i] - left[i] - 1;
            int area = width * heights[i];
            res= max(res, area);
        }
        return res;
    }
};

时间复杂度是$O(n)$，每次遍历中，每个元素最多进出栈一次。

一次遍历的优化

其实在我们每次pop的时候，就可以计算了！

因为既然我们维护的是不下降的单调栈，那么对于栈顶元素来说，栈的下一个元素肯定是小于等于他的。这样我们的左边界就可以确定了（尽管会有亢余计算）。

为了防止我们在计算的过程中栈为空，我们可以在heights数组的前后插入一个0。

class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        heights.insert(heights.begin(), 0);
        heights.push_back(0);
        int n = heights.size();
        stack<int> s;
        int res = 0;
        for (int i = 0; i < n; i++) {
            while(!s.empty() && heights[i] < heights[s.top()]) {
                int topHeight = heights[s.top()];
                s.pop();
                int curArea = (i - s.top() - 1) * topHeight;
                res = max(res, curArea);
            }
            s.push(i);
        }
        return res;
    }
};

时空复杂度和朴素做法是一样的。