---

84.柱状图中最大的矩形

思路

只有栈里从大到小的顺序，才能保证栈顶元素找到左右两边第一个小于栈顶元素的柱子。

所以本题单调栈的顺序正好与接雨水反过来。

此时大家应该可以发现其实就是栈顶和栈顶的下一个元素以及要入栈的三个元素组成了我们要求最大面积的高度和宽度

理解这一点，对单调栈就掌握的比较到位了。

除了栈内元素顺序和接雨水不同，剩下的逻辑就都差不多了，在题解42. 接雨水 (opens new window)我已经对单调栈的各个方面做了详细讲解，这里就不赘述了。

主要就是分析清楚如下三种情况：

情况一：当前遍历的元素heights[i]大于栈顶元素heights[st.top()]的情况
情况二：当前遍历的元素heights[i]等于栈顶元素heights[st.top()]的情况
情况三：当前遍历的元素heights[i]小于栈顶元素heights[st.top()]的情况

思路代码

func largestRectangleArea(heights []int) int {stack:=[]int{}heights=append([]int{0},heights...)heights=append(heights,0)res:=0for i:=0;i<len(heights);i++{for len(stack)>0&&heights[i]<heights[stack[len(stack)-1]]{mid:=stack[len(stack)-1]stack=stack[:len(stack)-1]left:=stack[len(stack)-1]res=max(res,heights[mid]*(i-left-1))}stack=append(stack,i)}return res
}func max(i,j int)int{if i<j{return j}return i
}

困难

开头结尾+0

---

今日收获

接雨水和柱状图在使用单调栈的时候都是为了判断左右两侧宽度的值。

总结

第一遍完结！！后续贪心，动态规划和单调栈需要加强！！！
也要掌握常用的手撕比如树的遍历