[题目][栈] 柱状图中的最大矩形

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

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

-> leetcode：柱状图的中最大矩形

暴力解法及寻找规律

最直觉的解题方法，就是往暴力解法上走，而用暴力解法我们可以理解题目的意思：

1. 遍历整个数组，遍历到本位置的时候，以本位置的数字作为高度；
2. 重新遍历该数组，如果碰到比当前高度小的地方，则记录当前的面积，重置当前的宽度；
3. 遍历完成后记录当前的面积；

这个思路写成代码：

class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        // 暴力
        int res{0};
        for (int i{0}; i<heights.size(); ++i) {
            int height = heights[i];
            int width{0};
            for (int j{0}; j<heights.size(); ++j) {
                if (height > heights[j]) {
                    res = max(width*height, res);
                    width = 0;
                    continue;
                }
                width += 1;
            }
            res = max(width*height, res);
        }
        return res;
    }
};

而当前的代码对于大型用例会超时，毕竟时间复杂度达到了O(N^2)。

避免遍历两遍，尽量只遍历一遍完成解答，则需要使用某些方法记录上一个状态，即典型的以空间换时间。

那么使用暴力解法了解到了这道题的本质，就可以选择对应的方案了。

根据示例：[2, 1, 5, 6, 2, 3]

按照暴力解法，可以观察到：

      6
    5 5
    4 4
    3 3   3
2   2 2 2 2
1 1 1 1 1 1

十分直观，凡是连续的相同的数字都可以组成矩形。

思考

所谓面积，而且是矩形的面积，就是找到长和高。

本题目当中寻找最大矩形就是找最大面积的矩形，题目当中，高基本可以很方便得获取到，就是数组中的数字，而大的数字可以作为较小的数字的一部分（反之则不行），因此需要考虑的地方在宽如何去确定。

暴力解法当中是先确定高，在逐步确定宽度，但一旦确定高之后会重新遍历一次整个柱型图，再确定高。

我们要避免回去再遍历一次，尽量在读取当前高度的时候就确定到能够获取的最大宽度，从而使得算法达到优化。

依旧按照示例，我们要做的事情如下：

1. 遍历到第一个元素是，即2，我们需要确定它最大的宽度，就是往下走，而下一个是1，无法成为2的最大宽度。那么第一个元素能够确定最大的宽度是1。
2. 第二个元素，是1，往前它可以使用2，往后可以到达最后一个，即最大宽度是6
3. 同理，往后续一步步地走到底部，一次性确定宽度。

我们需要做的是如何实现，这其中重要的是如何往前走和往后走，而不使用再次遍历的方法。

那么我们应该存储一个可以使用某种方法计算最大宽度（即现在高度的左右边缘）的值，显然无法使用数组中的值，而还能够使用的是其索引，我们先标注一下索引：

      6
    5 5
    4 4
    3 3   3
2   2 2 2 2
1 1 1 1 1 1
- - - - - - 
0 1 2 3 4 5

推断

现在推断：

1. 0索引，左右边缘是[0, 1)
2. 1索引，左右边缘是[0, 5]
3. 2索引，左右边缘是[2, 3]
4. 3索引，左右边缘是[3, 4)
5. 4索引，左右边缘是[2, 5]
6. 5索引，左右边缘是(4, 5]

注意()标记不包含，[]标记包含。

而如何实现这个索引的记录，我们尝试分析：

1. [0]时，数字2，暂时无法获取最大；
2. [1]时，数字1，比2小，可以确定2下边无法在往右走，则可以不理会2了，但1没有右边缘；
3. [2]时，数字5，比1大，还是无法确定两者；
4. [3]时，数字6，比5大，依旧无法确定；
5. [4]时，数字2，比6小，则确定6的边界到此处，同时5的边界也应该去确定，但不能在这一次确定，等待下一次，先确定6；
6. 此时回到[3]，已经确定该情况宽度，因此回到[2]，确定[2]的宽度；确定宽度的，则不再理会，继续往下走；
7. 此时我们疑惑[1]会不会确定边界，明显[4]中的2比1大，依旧无法确定1，则继续往下走；
8. 回到[4]，无法确定；
9. [5]时，数字3，比2大，因此无法确定2边界。但[5]是最后一个索引，因此可以确定3的边界，确定完成后，往回走；
10. 回到[4]，[5]中3比2大，则可以确定[4]的边缘了。
11. 而[2] [3]已经完成了边缘确定，跳过；
12. 回到[1]，最后一个元素，确定宽度；
13. 而[0]，已经确定，则跳过；
14. 流程已经完成
15. 输出结果

这过程中忽略了具体的计算内容，但可以感觉到这个过程是一个先进后出的过程，从5-7的时候已经发现了这个规律，后面也是一样的，那么我们可以确定使用栈可以实现这个记录。

计算

那么左右边缘如何去实现计算呢？

先将上诉分析的过程用栈模拟一下：

# 1. [0]:2 
stk: 0

# 2. [0]:2 [1]:1
1 < 2
确定 [0]，不要了
stk:
[1] 不确定
stk: 1

# 3. [1]:1 [2]:5
不确定
stk: 1 2

# 4. [1]:1 [2]:5 [3]:6
不确定
stk: 1 2 3

# 5. [1]:1 [2]:5 [3]:6 [4]:2
2 < 6
确定[3]，不要了
stk: 1 2
2 < 5
确定[2]，不要了
stk: 1
2 > 1
[1] 不确定
[4]不确定
stk: 1 4

# 6 [1]:1 [4]:2 [5]:3
[5]不确定
stk: 1 4 5

# 7 结束了，则弹出
stk: 1 4 5
[5] 确定，弹出
[4] 确定，弹出
[1] 确定，弹出

完成

大致流程确定，接下来添加计算过程：

l代表左边缘，r代表右边缘：

# 1. [0]:2 
stk: 0
>>>不计算

# 2. [0]:2 [1]:1
1 < 2
>>>[0]需要计算，左边无，则l:0
>>>右边是[1]，不包含，则r:1-1=0
>>>则width = r-l+1 = 1;
确定 [0]，不要了
stk:
[1] 不确定
stk: 1

# 3. [1]:1 [2]:5
不确定
stk: 1 2

# 4. [1]:1 [2]:5 [3]:6
不确定
stk: 1 2 3

# 5. [1]:1 [2]:5 [3]:6 [4]:2
2 < 6
>>>[3]需要计算，左边是[2]，但5<6，则l:2+1=3
>>>右边是[4],则r:4-1=3
>>>则width = r - l + 1 = 1;
确定[3]，不要了
stk: 1 2
2 < 5
>>>[2]需要计算，左边是[1]，但1<5，则l:1+1=2
>>>右边是[4]，则r:4-1=3
>>>则width=r-l+1=2
确定[2]，不要了
stk: 1
2 > 1
[1] 不确定
[4]不确定
stk: 1 4

# 6 [1]:1 [4]:2 [5]:3
[5]不确定
stk: 1 4 5

# 7 结束了，则弹出
此处运算法则不一致
stk: 1 4 5
>>>[5]需要计算，左边是[4]，但2<3，则l:4+1=5
>>>右边直接到底，r:5
>>>width=r-l+1=1;
[5] 确定，弹出
>>>[4]需要计算，左边是[1]，但1<2，则l:1+1=2
>>>右边直接到底,r:5
>>>width=r-l+1=4
[4] 确定，弹出
>>>[1]需要计算，左边无，则到头,l:0
>>>右边直接到底,r:5
>>>width=r-l+1=5
[1] 确定，弹出

完成

明显此处的计算分两类情况：

1. 遍历过程中；
2. 遍历完成，弹出栈的过程；

具体方案

1. 遍历过程中

触发条件：当前元素(index)小于栈顶元素，则开始确定栈顶元素的边缘（宽度）；

左边确定：弹出栈顶元素，则左边界为现栈顶元素+1；若无，则为0；

右边确定：index-1；

总宽度：右边确定-左边确定+1；

2. 弹出栈过程（遍历已经完成）

触发条件：栈顶元素（index）都需要确定；

左边确定：弹出栈顶元素，则左边边界为栈顶元素+1；若无，则为0；

右边确定：所要计算的柱形个数-1；

总宽度：右边确定-左边确定+1；

代码实现

好了，思路确定下来，可以开始写代码了。

class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        // 栈，存储元素
        std::stack<int> stk;

        // 最大索引
        int max_index=heights.size()-1;

        // 当前元素
        int current{0};
        // 栈顶元素
        int top{0};
        // 左右边界
        int left{0}, right{0};
        // 宽度
        int width{0};
        // 结果，面积
        int area{0};

        // 开始遍历
        for (int i{0}; i<=max_index; ++i) {
            current = i;
            // 如果栈为空 存入 无其他操作，跳过
            if (stk.empty()) {
                stk.push(current);
                continue;
            }

            top = stk.top();
            // 当前元素小于栈顶元素，触发条件
            while (!stk.empty() && (heights[current] < heights[top])) {
                stk.pop();
                left = stk.empty() ? 0 : stk.top() + 1;
                right = current - 1;
                width = right - left + 1;
                area = max(area, width * heights[top]);

                // 新一轮赋值
                top = stk.empty() ? 0 : stk.top();
            }

            stk.push(current);
        }

        // 弹出栈过程
        while (!stk.empty()) {
            top = stk.top();
            stk.pop();

            left = stk.empty() ? 0 : stk.top() + 1;
            right = max_index;
            width = right - left + 1;
            area = max(area, width*heights[top]);
        }

        return area;
    }
};

执行用时：12 ms, 在所有 C++ 提交中击败了93.35% 的用户
内存消耗：8.3 MB, 在所有 C++ 提交中击败了84.19% 的用户

愉快，解决！

如果有不正确的不清楚的，欢迎指正！