单调栈

本地单调栈的解法和接雨水的题目是遥相呼…84.柱状图中最大的矩形

题目要求给定

个非负整数用来表示柱状图中各个柱子的高度。

每个柱子彼此相邻且宽度为

单调栈

window)是找每个柱子左右两边第一个大于该柱子高度的柱子而本题是找每个柱子左右两边第一个小于该柱子的柱子。

这里就涉及到了单调栈很重要的性质就是单调栈里的顺序是从小到大还是从大到小。

在题解42.

window)中我讲解了接雨水的单调栈从栈头元素从栈头弹出到栈底的顺序应该是从小到大的顺序。

那么因为本题是要找每个柱子左右两边第一个小于该柱子的柱子所以从栈头元素从栈头弹出到栈底的顺序应该是从大到小的顺序

我来举一个例子如图

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

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

除了栈内元素顺序和接雨水不同剩下的逻辑就都差不多了在题解42.

接雨水

window)我已经对单调栈的各个方面做了详细讲解这里就不赘述了。

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

每一次入栈新元素时我是一直向左边比较比我小的柱子计算面积并且更新result的。

这个思路好神奇我还是没有太想明白中间在while中一直在pop是怎么继续比较的。

我个人认为一直在计算的是以每一个i为结尾right能够组成的最大矩形长度这样理解就对了。

因为如果当前的i对应的值是2之前有56。

即便2之后在出现6由于2存在的原因也无法组成以5、6为高度的矩形了所以2能够pop掉2之前所有比2大的st.top()。

class

st;heights.insert(heights.begin(),

0);heights.push_back(0);st.push(0);for

(int

弹出之后栈里没有元素了那么为了避免空栈取值直接跳过了计算结果的逻辑。

之后又将6