题目分析

本题我在多个平台都见过，可以说是一个比较经典的单调栈问题了，对于单调栈类型的题目，我们要深刻理解题目，然后找出单调的关系。小伙伴们注意理解我的解题过程。

优化暴力法

暴力法是指对于每一个数，都以该数为最右端点，寻找左边左端点的过程。也可以让该数为左端点，寻找右边右端点的过程。什么意思呢？样例中[2,1,5,6,2,3]，我们以2为右端点，2为左端点，可以得到面积为2的矩形。然后以1为右端点，1为左端点，1为右端点，2为左端点。即枚举左右端点，其中长度为左右端点索引之差 + 1，高度为区间内的最小值。

算法的**时间复杂度为$O(n^2)$，空间复杂度为$O(1)$**。

当然这个算法是无法通过样例的，我们可以对其优化。

优化1
如果res已知很大，假设为100，那么在枚举的过程中，高度上界 x 宽度都小于等于res的索引可以没有必要搜索了。如样例中[2,1,5,6,2,3]我们以6为右端点的时候，已经得到了10。当我们以2为右端点的时候，高度上界为2，宽度为5，即使在寻找左端点的过程中，高度没有下降都小于等于10，那么一定没有必要去搜索。直接进行下一个右端点3，寻找3的左端点时，当搜索到1时，高度降低为1，因此高度上界为1，宽度为6，即使在寻找左端点的过程中，高度是上界，都已经小于等于10，那么也可以停止搜索了。

上面的解释应该很好理解，类似于一种剪枝的过程。这个样例也会TLE，能否进行再一次的优化呢？

优化2
我们首先考虑一般情况下最大面积是什么情况？如果高度都差不多，最大面积是不是宽度越大，面积越大呢？因此宽度较大左右端点出现最大面积的概率更大一些。

因此我们要让res先变大，然后这样剪枝就更快，这句话非常重要。在优化1中，高度上界 x 宽度的值小于等于res，我们可以剪枝。那么res是不是越大，剪枝越快呢？在提交的样例中，有一个全是1的样例，大约有20000个。按照优化1的方法会超时，因为右端点为k时，res = k + 1，然后右端点为k + 1时，还是要遍历一次所有的情况。如果我们从后向前遍历右端点，第一次就令最后一个索引为右端点，那么第一次就可以得到res = 20001，然后就会每次都停止搜索，对于这个情况时间复杂度退化为线性。

算法的**时间复杂度为$O(n^2)$，空间复杂度为$O(1)$**。但是实际上会远远低于这个时间复杂度。

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

class Solution {
public:
     int largestRectangleArea(vector<int>& heights) {
        int res = 0;
        for (int i = heights.size() - 1; i >= 0; i--) {
            int h = heights[i];
            for (int j = i; j >= 0; j--) {
                h = min(h, heights[j]);
                if ((long long)h * (i + 1) <= res) { break; }
                res = max(res, h * (i - j + 1));
            }
        }
        return res;
    }
};

单调栈

在题目分析中说的，深刻理解题目，是啥意思呢？在本题中，我们发现如果是一个山谷型的区间，那么前面的无论有多高，都没有作用。如[5,2,4]这个区间，前面的5因为中间的2导致不起作用。无论前面的数字有多大，都不会影响结果。因此我们要维护一个单调递增的栈，当前面的数据较大时，因为它没有用，因此要将其弹出。然而在弹出时要对其进行计算，可能在该处产生最大面积。

这里为了计算最大的面积，因此单调栈中保存的是元素的下标。

如果当前下标中的元素小于栈顶对应的元素时，说明栈顶元素会被当前元素限制，可以计算以栈顶元素为高度能组成的矩形面积。因为栈中的索引都是递增的，所以矩形的宽度是当前元素所以i减去栈顶前一个元素的下标，因为栈顶前一个元素对应的值是小于栈顶元素的，不妨设前一个元素的下标为idx，则[idx + 1, i - 1]中的元素高度都是大于等于栈顶元素的。

因此弹出栈顶元素时，计算的矩形面积是栈顶 x (i - idx - 1)。

以样例[2, 1, 5, 6, 2, 3]进行说明，假如当前已经遍历到6这个元素，此时的递增栈为[1, 2]，要记得这个是索引。当6出现时，因为6大于5，5也就是原数组中第2个元素。因此将6对应的索引3压入栈中，栈为[1, 2, 3]。

此时遍历到元素2，因为2小于6，此时2后面的元素无法看到6，因此6是无效的元素，我们要将6对应的索引3弹出。在弹出时需要进行计算，此时2对应的索引为4，弹出3后，栈中还剩[1, 2]，因为索引2对应的元素5小于6，因此4 - 2 - 1是高度为6的矩形的边长。面积为6。

此时发现2小于5，因此继续上述操作，弹出索引2，栈中还剩[1]，索引为1的元素为1，比5小，说明高度为5的矩形的边长是4 - 1 - 1，面积为10。

为了让算法更加鲁棒和简单，有一个小技巧，在前面和后面都加一个元素0，这样直接使用该算法即可，不需要考虑首尾元素的判断。

如果不加前面的0，可能弹出元素后，栈为空，如[2, 1]这个例子，1出现会将2弹出，这时栈中为空，矩形的边长不好计算。

如果后面不加0，可能最后一个元素是递增的，如[1, 2]这个例子，直接将2的索引1加入栈中，栈中元素为[0, 1]，然后算法就结束了，需要在循环后面单独判断，如果最后元素为0，那么会向前寻找到上一个0出现才会结束，算法结束后直接返回最大值即可。

这个小技巧需要小伙伴们多多琢磨一下，有时候算法也很难全部讲清楚，我上面说的解题过程比较绕，需要要伙伴跟着我的叙述在纸上一步一步写一些，这样做几遍可能就清晰了。

算法的**时间复杂度为$O(n)$，空间复杂度为$O(n)$**。

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        vector<int> newHeights(heights.size() + 2);
        copy(heights.begin(), heights.end(), newHeights.begin() + 1);
        vector<int> s;
        int res = 0;
        for (int i = 0; i < newHeights.size(); i++) {
            while (!s.empty() && newHeights[s.back()] > newHeights[i]) {
                int idx = s.back();
                s.pop_back();
                res = max(res, (i - s.back() - 1) * newHeights[idx]);
            }
            s.push_back(i);
        }
        return res;
    }
};

这个题目在2022年9月又重新做了一次，现在给出java的题解。

class Solution {
    public int largestRectangleArea(int[] heights) {
        int n = heights.length;
        int[] newHeight = new int[n + 2];
        System.arraycopy(heights, 0, newHeight, 1, n);
        LinkedList<Integer> list = new LinkedList<>();
        int res = 0;
        for (int i = 0; i < n + 2; i++) {
            while (!list.isEmpty() && newHeight[i] < newHeight[list.getLast()]) {
                int h = newHeight[list.pollLast()];
                int idx = list.getLast();
                res = Math.max(res, h * (i - idx - 1));
            }
            list.add(i);
        }
        return res;
    }
}

刷题总结

单调栈类型的题目，代码很简单，而且有固定的写法，都是一个for循环，内嵌一个while循环。但是如何将问题抽象出一个单调栈是非常困难的。