[题目][栈] 柱状图中的最大矩形
给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。
求在该柱状图中，能够勾勒出来的矩形的最大面积。
暴力解法及寻找规律
最直觉的解题方法，就是往暴力解法上走，而用暴力解法我们可以理解题目的意思：
- 遍历整个数组，遍历到本位置的时候，以本位置的数字作为高度；
- 重新遍历该数组，如果碰到比当前高度小的地方，则记录当前的面积，重置当前的宽度；
- 遍历完成后记录当前的面积；
这个思路写成代码：
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十分直观，凡是连续的相同的数字都可以组成矩形。
思考
所谓面积，而且是矩形的面积，就是找到长和高。
本题目当中寻找最大矩形就是找最大面积的矩形，题目当中，高基本可以很方便得获取到，就是数组中的数字，而大的数字可以作为较小的数字的一部分（反之则不行），因此需要考虑的地方在宽如何去确定。
暴力解法当中是先确定高，在逐步确定宽度，但一旦确定高之后会重新遍历一次整个柱型图，再确定高。
我们要避免回去再遍历一次，尽量在读取当前高度的时候就确定到能够获取的最大宽度，从而使得算法达到优化。
依旧按照示例，我们要做的事情如下：
- 遍历到第一个元素是，即2，我们需要确定它最大的宽度，就是往下走，而下一个是
1，无法成为2的最大宽度。那么第一个元素能够确定最大的宽度是1。 - 第二个元素，是1，往前它可以使用2，往后可以到达最后一个，即最大宽度是6
- 同理，往后续一步步地走到底部，一次性确定宽度。
我们需要做的是如何实现，这其中重要的是如何往前走和往后走，而不使用再次遍历的方法。
那么我们应该存储一个可以使用某种方法计算最大宽度（即现在高度的左右边缘）的值，显然无法使用数组中的值，而还能够使用的是其索引，我们先标注一下索引：
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推断
现在推断：
0索引，左右边缘是[0, 1)1索引，左右边缘是[0, 5]2索引，左右边缘是[2, 3]3索引，左右边缘是[3, 4)4索引，左右边缘是[2, 5]5索引，左右边缘是(4, 5]
注意()标记不包含，[]标记包含。
而如何实现这个索引的记录，我们尝试分析：
[0]时，数字2，暂时无法获取最大；[1]时，数字1，比2小，可以确定2下边无法在往右走，则可以不理会2了，但1没有右边缘；[2]时，数字5，比1大，还是无法确定两者；[3]时，数字6，比5大，依旧无法确定；[4]时，数字2，比6小，则确定6的边界到此处，同时5的边界也应该去确定，但不能在这一次确定，等待下一次，先确定6；- 此时回到
[3]，已经确定该情况宽度，因此回到[2]，确定[2]的宽度；确定宽度的，则不再理会，继续往下走； - 此时我们疑惑
[1]会不会确定边界，明显[4]中的2比1大，依旧无法确定1，则继续往下走； - 回到
[4]，无法确定； [5]时，数字3，比2大，因此无法确定2边界。但[5]是最后一个索引，因此可以确定3的边界，确定完成后，往回走；- 回到
[4]，[5]中3比2大，则可以确定[4]的边缘了。 - 而
[2][3]已经完成了边缘确定，跳过； - 回到
[1]，最后一个元素，确定宽度； - 而
[0]，已经确定，则跳过； - 流程已经完成
- 输出结果
这过程中忽略了具体的计算内容，但可以感觉到这个过程是一个先进后出的过程，从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. 遍历过程中
触发条件：当前元素(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% 的用户
愉快，解决！
如果有不正确的不清楚的，欢迎指正！
