写题目的时候，一般用双端队列来模拟栈。

双端队列：
Deque<> queue = new LinkedList<>();
// 添加到队尾
deque.offerLast(1);  // 推荐，返回true/false
// 添加到队首
deque.offerFirst(2); // 推荐
// 移除队首
first = deque.pollFirst();        // 推荐，返回null
// 移除队尾
last = deque.pollLast();          // 推荐
// 查看队首
first = deque.peekFirst();        // 推荐，返回null
// 查看队尾
last = deque.peekLast();         // 推荐
deque.isEmpty();      // 是否为空
deque.size();         // 元素个数
deque.contains(1);    // 是否包含
deque.clear();        // 清空
deque.removeFirstOccurrence(1);  // 移除第一个出现的1

有效的括号

遇到右括号就和栈顶的判断下，如果匹配就出栈，最后看下栈是不是空。数据结构Map和Stack。

class Solution {
    public boolean isValid(String s) {
        if(s.length() <= 1 || s.length() % 2 == 1){
            return false;
        }
        Map<Character, Character> mp = new HashMap<>();
        mp.put('(',')');
        mp.put('[',']');
        mp.put('{','}');
        Stack<Character> st = new Stack<>();
        for(int i = 0; i < s.length(); i++){
            char c = s.charAt(i);
            // 如果是左括号
            if(mp.get(c) != null){
                st.push(c);
            }else{
                // 右括号 判断情况
                if(st.isEmpty() || mp.get(st.peek()) != c){
                    return false;
                }
                st.pop();
            }
        }
        return st.isEmpty();
    }
}

最小栈

需用辅助栈存对应的最小值。当一个元素要入栈时，我们取当前辅助栈的栈顶存储的最小值，与当前元素比较得出最小值，将这个最小值插入辅助栈中。

class MinStack {

    Deque<Integer> st;
    Deque<Integer> minst;
    public MinStack() {
        st = new LinkedList<Integer>();
        minst = new LinkedList<Integer>();
        minst.offerLast(Integer.MAX_VALUE);
    }
    
    public void push(int val) {
        st.offerLast(val);
        minst.offerLast(Math.min(minst.peekLast(), val));
    }
    
    public void pop() {
        st.pollLast();
        minst.pollLast();
    }
    
    public int top() {
        return st.peekLast();
    }
    
    public int getMin() {
        return minst.peekLast();
    }
}

字符串编码

递归。模拟题，看代码理解比较方便。关联知识点：StringBuilder的用法。

class Solution {
    int index = 0;
    public String decodeString(String s) {
        return dfs(s);
    }

    public String dfs(String s){
        StringBuilder res = new StringBuilder();
        // 当匹配到]时退出当层递归
        while(index < s.length() && s.charAt(index) != ']'){
            // 如果是数字的话
            int num = 0;
            if(s.charAt(index) <='9' && s.charAt(index) >= '0'){
                num = getNum(s);
                // 略过左右括号 递归调用
                index++;
                String inner = dfs(s);
                index++;
                // 拼凑出结果
                for(int i = 0; i < num; i++){
                    res.append(inner);
                }
            }else{
                // 左括号前面一定有数字 所以非数字的情况只能是字母
                res.append(s.charAt(index));
                index++;
            }
        }
        return res.toString();
    }

    public int getNum(String s){
        int num = 0;
        while(index <s.length() && s.charAt(index) <='9' && s.charAt(index) >= '0' ){
            num = num * 10 + s.charAt(index) - '0';
            index++;
        }
        return num;
    }
}

每日温度

单调栈。关键要知道单调栈要存什么数据。

单调栈的本质，是一个记录已经遍历过元素特征的数据结构。并支持和当前的元素进行某种对比。

单调栈：遍历列表，从第一个开始，比上一个小就入栈，否则就出栈直到栈顶元素大于当前的列表元素或者栈为空，维持一个单调递减的栈。本题，单调栈存的是单调递减的温度，遇到比栈顶高的温度，就能得到两个日期差了。

class Solution {
    public int[] dailyTemperatures(int[] temperatures) {
        int n = temperatures.length;
        int[] res = new int[n];
        // 栈里存的是索引
        Deque<Integer> dq = new LinkedList<>();
        int index = 0;
        for(int i = 0; i<n; i++){
            int temp = temperatures[i];
            // 当前的温度大于栈顶的温度 可以更新了
            // 一个例子 索引里面可能存的是 0(60)、1(55)、2(50)，遇到了3(57)
            // 不断退出索引 直到遇到0(60)
            while(!dq.isEmpty() && temp > temperatures[dq.peekLast()]){
                // 栈顶的索引
                int preIndex = dq.pollLast();
                res[preIndex] = i - preIndex;
            }
            // 栈顶的温度 大于当前的温度 索引入栈
            dq.offerLast(i);
        }
        return res;
    }
}

柱状图中的最大矩形

矩形的宽度由该柱子向左右延伸到第一个比它矮的柱子决定，问题转化为：对每个柱子，找到左右边界。维护一个单调递增栈，当遇到栈顶大于遍历的下标的时候，说明找到了右侧边界，左边界是出栈后的新栈顶，右边界是当前索引-1。

class Solution {
public int largestRectangleArea(int[] heights) {
    // 哨兵：首尾加0，保证所有柱子都能被处理
    int[] newHeights = new int[heights.length + 2];
    System.arraycopy(heights, 0, newHeights, 1, heights.length);
    heights = newHeights;
    
    Deque<Integer> stack = new LinkedList<>();
    int maxArea = 0;
    
    for (int i = 0; i < heights.length; i++) {
        // 当前柱子比栈顶矮，说明栈顶柱子的右边界找到了
        while (!stack.isEmpty() && heights[i] < heights[stack.peekLast()]) {
            int height = heights[stack.pollLast()];  // 栈顶柱子高度
            int left = stack.peekLast();  // 左边界即栈顶
            int width = i - left - 1;  // 宽度
            maxArea = Math.max(maxArea, height * width);
        }
        stack.offerLast(i);
    }
    
    return maxArea;
}

}