代码随想录day60:贪心算法｜84.柱状图中最大的矩形

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;
    }
};