Stack

Stack

1.单调栈

(1) 使用单调栈的情景：

a. 输出的string的字母按照lexicographical order(Leetcode #316)

b. 处理的问题的具有单调性，比如Leetcode #456, #496

(2) 模板

// 单调递增栈
for (int num : nums) {
            while (!stack.isEmpty() && stack.peek() > num) {
               stack.pop();
            }
            stack.push(num);
        }

// 单调递减栈
for (int num : nums) {
            while (!stack.isEmpty() && stack.peek() < num) {
               stack.pop();
            }
            stack.push(num);
        }

2. 树的遍历顺序

涉及到树的三种遍历顺序问题也很适合用stack， 比如Leetcode #173和#255

3. 表达式转换

许多表达式适合用stack，尤其之前的计算结果之后可能需要，比如Leetcode #150, #224 和 #439

4. Simulate Recursion

许多表达式适合用stack，尤其之前的计算结果之后可能需要