单调栈

5月5日总结了单调队列的用法,今天来单调栈。

单调栈

单调栈

栈顶比当前值小的,栈顶pop,知道满足从上到下严格递减即可。

从上面的单调栈可以得出的是:

当前的值向左查,第一个比他小的索引,以及向右查第一个比他小的索引。

向左第一个比他小的值在栈中他的下面。

向右查第一个比他小的值是,当他弹出时要插入的值或者是后面没有比他小的。

  • 84题。柱状图中的最大矩形面积。

单调栈

根据单调栈,可以得出在弹出时得出:

向左查,第一个比他小的,和向右查,第一个比他小的。

所以 以该高度计算的矩形面积可以得到。

11题。42题。85题。