算法笔记(二):栈与单调栈

栈

leetcode里easy和medium的题目往往考察数据结构超过算法，即使到了hard，也很关注数据结构本身，而且都是常见的数据结构。这与leetcode面向interview有关系，无怪乎ACMer看不上。
各种数据结构又以栈的使用最广，如设计题目中的232. 用栈实现队列,232. 用栈实现队列,155. 最小栈。其中155题很是巧妙，在一个栈里同时保存当前值和当前值与当前的最小值的差值，实现在O(1)的时间获取栈的当前最小值。当然，栈更多的使用场景是辅助实现一些算法功能，比如实现前中后序迭代遍历二叉树，又比如利用单调栈将蛮力算法的复杂度降低到O(n)。

单调栈

84. 柱状图中最大的矩形是利用单调栈将蛮力算法的复杂度降低到O(n)的典型题目。核心代码如下:

              for (int i = 1; i < len; i++) {
                  while (cs[path.peekLast()]>cs[i]){
                      //i点为右侧,取出最高点后，path.getLast()为左侧
                      //(左右都比当前点要小，所以以当前点为高度的面积的宽度为右侧-左侧)
                      max=Math.max(max,cs[path.pollLast()]*(i-path.peekLast()-1));
                      
                  }
                  path.addLast(i);
      
              }

代码很简单，然而这个题目的难度是hard。
算法的核心是找到对于每个圆柱，找到连续的最左和最右比自己高的圆柱，相减为宽度，乘以圆柱本身也就是面积，依次遍历所有圆柱，比较出最大的面积即可。蛮力算法即对每个圆柱，都向左和向右遍历，复杂度是O(n^2).而利用单调栈的特性，可以将向左和向右遍历这个步骤去掉。向右遍历每个圆柱(i)，如果圆柱比栈里最后一个圆柱要高，将此圆柱(i)压入栈，继续遍历；如果圆柱比栈里最后一个圆柱要低，由于此时单调性被破坏，暂停，从栈里不停取出圆柱(path.pollLast()),宽度为i-path.peekLast()-1(由于前一步执行的是poll，目前剩余的最后一个也就是比圆柱(i)矮或相等的圆柱的下标，两个下标相减正好是中间的宽度)，得到面积，比较最大值。一直到栈里最后的圆柱(path.pollLast())高度大于圆柱(i)，单调性得以恢复，将此圆柱(i)压入栈，继续向前遍历。如此一遍即可得出最大面积。
单调栈借鉴了数学里单调性的定义，语言描述较为生涩，实际在纸张上画出则非常容易理解，在左右两侧有高度为-1的哨兵的情况下，由于单调栈是单调递增，所以单调栈内部的元素共享统一的最右侧下标，而每个圆柱的最左侧下标也就是单调栈里保存的前一个圆柱。另外 [85. 最大矩形]是这个题的二维版本，无非是在此基础上做一个简单的判断+二维循环。

Is this article useful to you? How about buy me a coffee ☕ ?