84. Largest Rectangle in Histogram
进行优化，如果我们想获得left就给他left即可，我们只需要在求宽度的时候用到left,而没必要修改原数组。
所以给栈插入一个虚拟索引-1
思考过程：
left应该为多少呢？
首先确定left是什么？ left是索引，是左边界的柱子
那第一个元素是8的时候，他的面积怎么求的，不就是宽度1 * 高度8.
他的左边界应该是多少呢？
根据公式可得：
width = 1 - left - 1 == 1，可知left == -1! 害！这不就是索引0的左边吗？索引为-1
相当于给数组第一个元素左侧插入了一个虚拟元素嘛。
func largestRectangleArea(heights []int) int {
heights = append(heights, 0)
stack := []int{-1}
maxArea := 0
for i, h := range heights {
for len(stack) > 1 && h < heights[stack[len(stack)-1]] {
height := heights[stack[len(stack)-1]]
stack = stack[:len(stack)-1]
width := i - stack[len(stack)-1] - 1
maxArea = max(maxArea, height*width)
}
stack = append(stack, i)
}
return maxArea
}
详解版
// 找每个柱子左右两侧第一个小于该柱子的柱子
// 找小的，需要维护一个单调递增栈
func largestRectangleArea(heights []int) int {
// 结尾添加最小值0，让heights中最后一个元素可以出栈，计算它的面积！
// 而且他还可以让所有留在栈中的元素都出栈[1,2,2,2,2,3],第一个2可是面积最大值，不能不计算！
heights = append(heights, 0)
stack := []int{-1} // 防止栈底元素弹出时，找不到左柱子
maxArea := 0
for i, h := range heights {
// 维护递增栈，寻找两侧第一个小的竹子
// 注意栈中第一个元素是-1,不属于heights中，不能进行判断，所以栈长度要>1
for len(stack) > 1 && h < heights[stack[len(stack)-1]] { // 此时i为右侧第一个小于栈顶的，为右侧柱子
height := heights[stack[len(stack)-1]] // 栈顶元素高度
stack = stack[:len(stack)-1] // 出栈
//计算面积
left := stack[len(stack)-1] // 此时栈顶为左侧第一个小于弹出的栈顶的，为左侧柱子
width := i - left - 1 // 求两个柱子中间的距离，要-1
maxArea = max(maxArea, height*width)
}
stack = append(stack, i) // 当前柱子入栈，记录索引值
}
return maxArea
}
Questions
问几个问题来检验一下自己的理解吧！
1. 为什么在heights添加最后一个元素0？
不仅可以让最后一个元素出栈，而且可以让所有的元素都可以出栈，可以计算每个元素的高度的面积
当heights=[1,2,2,2,2,2,2,3]中，如果不添加最后一个元素，单调递增，所有元素都不可以出栈！可第一个2是我们要找最大面积哦！
2. stack栈中为什么要插入一个-1？
这是一种优化哦！
3. 栈底元素一定是heights中第一个元素吗？
不一定
4. 判断栈操作中，为什么要判断栈长度>1而不是栈非空？
5. 卡哥代码中为什么可以不判断栈是否为空？
while (heights[i] < heights[st.top()])为什么可以不判断栈是否为空？
// 版本二
class Solution {
public:
int largestRectangleArea(vector<int>& heights) {
stack<int> st;
heights.insert(heights.begin(), 0); // 数组头部加入元素0
heights.push_back(0); // 数组尾部加入元素0
st.push(0);
int result = 0;
for (int i = 1; i < heights.size(); i++) {
while (heights[i] < heights[st.top()]) {
int mid = st.top();
st.pop();
int w = i - st.top() - 1;
int h = heights[mid];
result = max(result, w * h);
}
st.push(i);
}
return result;
}
};
