Stack

单调栈模板及应用

for (int i = 0; i < array.length; i++) {
  //这里的大小关系比较取决于我们是在使用递增栈还是递减栈， 比如这里是递增栈
  whhile (!stack.isEmpty() && array[stack.peek()] > array[i]) {
    // do sth
  }
  stack.push(i);
}

//补刀，因为栈里面可能还剩下element没有被pop
while (stack.isEmpty()) {
  //因为这里面没有右边的元素了，所以我们直接pop，逻辑和上面类似
  // do sth
}

一般来说，如果我们想要O(1)时间查询某个数两边第一个比他大或者第一个比他小的数，那么可以使用递增递减栈。

题目

往回走

• Leetcode 71. Simplify Path

递增递减栈

• Leetcode 84. Largest Rectangle in Histogram
• Leetcode 85. Maximal Rectangle
• Leetcode 321. Create Maximum Number