Descending Stack

即Stack中只包含递减的元素，适用于非有序数组，求数组中元素大小关系的问题。 [Daily Temperatures] 这道题目里数组是无序的，而运用递减stack，这样当新的元素与stack元素比较时候

• 如果大于栈顶元素，则满足要求，当前元素即为大于栈顶元素的第一个数。并且可以一直跟新的栈顶元素进行比较，更新答案，直到遇到比他大的
• 如果小于栈顶元素，那么直接加入stack，这样仍然保持着一个descending stack

class Solution {
    class Pair {
        int pos;
        int val;
        public Pair(int val, int pos) {
            this.val = val;
            this.pos = pos;
        }
    }
    public int[] dailyTemperatures(int[] T) {
        int[] ans = new int[T.length];
        Stack<Pair> stack = new Stack<>();

        for (int i = 0; i < T.length; i++) {            
            while (!stack.isEmpty() && T[i] > stack.peek().val) {
                Pair p = stack.pop();
                ans[p.pos] = i - p.pos;                
            }
            stack.push(new Pair(T[i], i));                
        }        
        return ans;
    }
}

遇到反向类的问题，比如single LL,要从尾到头的遍历

Add Two Number II

Stack 的另一个应用就是当题目所问涉及到先后的相对关系。（必须要先有a再有b之类的）

Valid Parentheses

• 这题想到stack的原因是在右括号出现之前，一定要有对应的左括号出现，并且这个左括号必须是最近的一个
• 在stack.pop之前，要确保stack不是空的

class Solution {
    public boolean isValid(String s) {
        Stack<Character> stack = new Stack<>();

        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (c == '(' || c == '[' || c == '{') {
                stack.push(c);
            } else if (c == ')' || c == ']' || c == '}') {
                if (stack.isEmpty()) 
                    return false;
                String str = "" + stack.pop() + c;
                if (!str.equals("()") && !str.equals("[]") && !str.equals("{}")) 
                    return false;
            }
        }
        return stack.isEmpty();
    }
}