Stack

Stack Overview

Implementation Stack

• Implement Stack
• Implement Stack using Queues
  • 不用每次都来回倒，可以把一部分先放在暂存的里面的，然后判断是否为空，再将另一个stack里的元素倒进来。
• Implement a stack by two queues

Monotonic Stack (单调栈)

单调栈主要作用是在O(n)的时间内求某个元素的下一个最值，或者某元素前一个的最值，衍生而来就有从前往后和从后往前两种写法。针对单调栈问题第一步无疑是确定这是一个单调增还是单调减 （当然最难的是怎么发现这是一个单调栈问题）

Related Questions

• Next Greater Element
• Next Greater Element II
• Next Greater Node In Linked List
• Daily Temperatures
• Largest Rectangle in Histogram
  • 分别求左边和右边的第一个最小值，然后算面积
  • 也可以改进成1 pass的方法
• Trapping Rain Water
  • 维护一个单调减stack
  • 相比于上面一题，这里的结果计算更难理解一点，要分层计算
• Container With Most Water
  • 虽然不是单调栈问题，但和上面一个背景
• Trapping Rain Water II *
• Sum of Subarray Minimums
• Sum of Subsequence Widths*
• Online Stock Span
• Remove Duplicate Letters
• Maximal Rectangle
• Remove K Digits
• Max Tree

Parse String

• Valid Parentheses
• Longest Valid Parentheses
• Minimum Remove to Make Valid Parentheses
• Minimum Add to Make Parentheses Valid
• Decode String
  • 思路不难，小细节很多
  • Integer.valueOf(char) 返回的是该char variable的asics值
  • 从设计上来说，stack里放入StringBuilder用来中转，比放入String最后再生成结果方便
  • 当然也可以直接用递归
• Simplify Path
  • 如果不用split就要考虑贼多的cornercase
• Score of Parentheses
• Evaluate Reverse Polish Notation
• Basic Calculator
• Basic Calculator II
• Basic Calculator III*
• Basic Calculator IV*
  • 应该不用这么丧心病狂吧

Iterator

不知道这个部分算哪类了，就放在Stack里面吧。先看看Java是如何实现Iterator的，主要有hasNext(), Next(), Remove() 三个函数，一般Remove()不需要额外设计。

Related Questions

• Flatten Nested List Iterator
• Binary Search Tree Iterator
  • 在Binary Tree 时会写，放stack里就不会写了， 衰==。。
• Peeking Iterator
• Zigzag Iterator
• Design Compressed String Iterator
• Iterator for Combination*
  • 不用递归prebuild还是有点难度的
• RLE Iterator

Others

• Min Stack
• Maximal Rectangle *
• Exclusive Time of Functions
  • 很有意思的题目
  • follow up : what if multi-core cpu?

Code

单调栈

 1// from begin to end
 2for (int num : nums2){
 3    while (!stack.isEmpty() && stack.peek() < num){
 4        int cur = stack.pop();
 5        // record rst
 6    }
 7    stack.push(num);
 8}
 9
10// from end to begin
11for (int i = nums2.length - 1; i >= 0; i--){
12    int num = nums2[i];
13    while (!stack.isEmpty() && stack.peek() <= num){
14        stack.pop();
15    }
16    if (!stack.isEmpty()){
17        // record rst
18    }
19    stack.push(num);
20}