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 := 0for 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 := 0for i, h := range heights {// 维护递增栈，寻找两侧第一个小的竹子// 注意栈中第一个元素是-1,不属于heights中，不能进行判断，所以栈长度要>1for 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       // 求两个柱子中间的距离，要-1maxArea = 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); // 数组头部加入元素0heights.push_back(0); // 数组尾部加入元素0st.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;}
};