LeetCode 栈
- LC20. 有效的括号">LC20. 有效的括号
- LC155. 最小栈">ArrayList存放最小值 LC155. 最小栈
- 150. 逆波兰表达式求值">后序遍历入栈150. 逆波兰表达式求值
- 232. 用栈实现队列">缓存栈232. 用栈实现队列
- 388. 文件的最长绝对路径">后入先出 388. 文件的最长绝对路径
单调栈
- 每日温度">普通单调栈每日温度
- 456. 132 模式">特殊意义单调栈456. 132 模式
- 503. 下一个更大元素 II">典型单调栈 + 循环数组503. 下一个更大元素 II
- 42. 栈的压入、弹出序列">栈中数据的意义 42. 栈的压入、弹出序列
  - 正确思路
- 42. 接雨水 - 力扣">特殊单调栈42. 接雨水 - 力扣

LeetCode 栈

LC20. 有效的括号

class Solution {
    public boolean isValid(String s) {
        //使用栈
        Stack<Character> stack = new Stack<>();
        for (int i = 0; i < s.length(); i ++){
            if (s.charAt(i) == '(')
                stack.push(s.charAt(i));
            if (s.charAt(i) == '[')
                stack.push(s.charAt(i));
            if (s.charAt(i) == '{')
                stack.push(s.charAt(i));
            if ( s.charAt(i) == ')'){
                if (!stack.empty() && stack.peek() == '(')
                    stack.pop();
                else return false;
            }
            if (s.charAt(i) == ']'){
                if (!stack.empty() && stack.peek() == '[')
                    stack.pop();
                else return false;
            }
            if (s.charAt(i) == '}'){
                if (!stack.empty() && stack.peek() == '{')
                    stack.pop();
                else return false;
            }
        }
        if (stack.empty())
            return true;
        return false;
    }
}

ArrayList存放最小值 LC155. 最小栈

思路

使用ArrayList存放到目前为止，栈中的最小值。

每次push入栈的时候，把栈的最小值插入ArrayList中

pop出栈的时候，删除对应的ArrayList最后一个值

getMin返回ArrayList的最后一个值

class MinStack {
    ArrayList<Integer> list;
    Stack<Integer> s;
    int idx; int minv = Integer.MAX_VALUE;
    public MinStack() {
        list = new ArrayList();
        s = new Stack<Integer>();
        idx = -1;
    }
    public void push(int x) {
        s.push(x); 
        minv = Math.min(x, idx >= 0 ? list.get(idx) : Integer.MAX_VALUE);
        list.add(minv); 
        idx++;
    }
    public void pop() {
        list.remove(idx--);
        s.pop();
    }
    public int top() {
        return s.peek();
    }
    public int min() {
        return list.get(idx);
    }
}

后序遍历入栈150. 逆波兰表达式求值

表达式树

表达式中所有数字节点都是叶子节点
所有操作数节点都是内部节点
后缀表达式通过后序遍历树的方式创建
中缀表达式通过中序遍历树的方式创建
我们发现，进行后序遍历的时候，如果根节点被创建了，那么它的左右子节点都被创建了。

通过这些性质，我们可以通过给定的后续表达式：

每当遇到一个点，就加入栈中
每当我们遇到一个操作数（根节点），就可以把它的左右子节点（都pop出栈，计算这一个子树表达式的值）

class Solution {
    String[] oper = new String[]{"+", "*", "/", "-"};
    public int evalRPN(String[] tokens) {
        //后缀转中缀表达式
        Stack<Integer> s = new Stack<Integer>();
        HashSet<String> op = new HashSet<String>();
        for (int i = 0; i < 4; i ++)
            op.add(oper[i]);
        int n = tokens.length;
        for (int i = 0; i < n; i ++){
            if (!op.contains(tokens[i])){
                s.push(Integer.valueOf(tokens[i]));
            }
            else{
                Integer res = new Integer(0);
                Integer n1 = s.pop();
                Integer n2 = s.pop();
                String op1 = tokens[i];
                if (op1.equals("+")) res = n1 + n2;
                else if (op1.equals("-")) res = n2 - n1;
                else if (op1.equals("*")) res = n1 * n2;
                else res = n2 / n1;
                s.push(res);
               // System.out.println(s);
            }
        }
        return s.peek();
    }
}

缓存栈232. 用栈实现队列

思路

建立两个栈一个作为缓存栈s2,一个是实际操作栈s1
push ：就对s1进行push和empty的操作
pop ：需要s1把除了栈顶的所有元素都pop，并放入s2中，再pop s1的栈顶元素，最后把s2元素压回s1
peek ：需要s1把除了栈顶的所有元素都pop，并放入s2中，返回s1的栈顶元素t，最后把s2元素压回s1,
empty s1.isEmpty
均摊操作还是o(1)的

class MyQueue {
    Stack<Integer> s1, s2;
    /** Initialize your data structure here. */
    public MyQueue() {
        s1 = new Stack<Integer>();
        s2 = new Stack<Integer>();
    }
    /** Push element x to the back of queue. */
    public void push(int x) {
        s1.push(x);
    }
    /** Removes the element from in front of queue and returns that element. */
    public int pop() {
       while (s1.size() > 1){
            s2.push(s1.pop());
        }
        int t = s1.pop();
        while (!s2.isEmpty())
            s1.push(s2.pop());
        return t;
    }
    /** Get the front element. */
    public int peek() {
        while (s1.size() > 1){
            s2.push(s1.pop());
        }
        int t = s1.peek();
        while (!s2.isEmpty())
            s1.push(s2.pop());
        return t;
    }
    /** Returns whether the queue is empty. */
    public boolean empty() {
        return s1.isEmpty();
    }
}
/**
 * Your MyQueue object will be instantiated and called as such:
 * MyQueue obj = new MyQueue();
 * obj.push(x);
 * int param_2 = obj.pop();
 * int param_3 = obj.peek();
 * boolean param_4 = obj.empty();
 */

后入先出 388. 文件的最长绝对路径

自己的思路

遍历的时候计算\t的个数，如果是递增的，就把\t后的字符串长度加入Stack中
如果不是递增的，就统计长度 = stack中字符的长度 + stack.size() - 1，更新maxv pop掉所有元素
最后要再计算一次stack中的字符长度（最后一个字符）
最后最长路径要加上最开始的根目录字符
Stack存放根目录到父目录的长度和父目录的级数
t就是目录级数 0是根目录

由于我没有判断最后一个是否为文件，也没有加入根目录，当最长路径没有文件或者只出现根目录的时候就会报错

class Solution {
    public int lengthLongestPath(String input) {
        Stack<List<Integer>> s = new Stack<List<Integer>>();
        int n = input.length();
        int t = 0, st = -1, ed = -1, root = 0;
        int maxv = Integer.MIN_VALUE;
        for (int i = 0; i < n; i ++){
            if (root == 0 && input.charAt(i) == '\n') root = i + 1;
            if (input.charAt(i) == '\t'){
                t ++;
                st = i + 1;
                continue;
            }
            if (i - 1 >= 0 && (t > 0 && input.charAt(i) == '\n') || i == n - 1){
                if (i == n - 1) ed = i;
                else ed = i - 1;
            }
            if (st != -1 && ed != -1){
                int len = ed - st + 1;
                if (s.isEmpty() ||  t > s.peek().get(1)){
                    List<Integer> list= new ArrayList<Integer>();
                    list.add(len);
                    list.add(t);
                    s.push(list);
                }
                else{
                    maxv = Math.max(maxv, total(s));
                    List<Integer> list= new ArrayList<Integer>();
                    list.add(len);
                    list.add(t);
                    s.push(list);
                }
                t = 0;
                st = -1;
                ed = -1;
            }
        }
        return Math.max(maxv, total(s)) + root;
    }
    public int total( Stack<List<Integer>> s){
        int totalnum = 0;
        int num = s.size();
        while (!s.isEmpty()){
            List<Integer> tmp = s.pop();
            totalnum += tmp.get(0);
        }
        return totalnum + num - 1;
    }
}

yxc的思路

遍历的时候遇到\t 更新级数t，更新下一次坐标
1. 如果级数t >= stack.size() ，把\t后的字符串长度加入Stack中，更新当前路径的长度sum
2. 如果t < stack.size(),说明当前文件不是这个目录下的，回溯，更新为当前文件路径sum，当最后一个是文件的时候，计算最终答案是sum + stack.size() - 1 ,否则为上一个路径的sum

可以明显看到yxc的思路非常的简化，代码量少了一半

具体原因是考虑到了回溯的情况，当前级数 <= 栈中存放的级数，就回溯，否则加入栈并计算最值

class Solution {
    public int lengthLongestPath(String input) {
        Stack<Integer> stack = new Stack<Integer>(); 
        int n = input.length();
        int maxv = 0, sum = 0;
        for (int st = 0; st < n;){
            int t = 0;
            while (st < n && input.charAt(st) == '\t'){
                t++; st++;
            }
            int ed = st;
            while (ed < n && input.charAt(ed) != '\n'){
                ed ++;
            }
            int len = ed - st;
            while (stack.size() > t){
                sum -= stack.peek(); stack.pop(); 
            }
            stack.push(len); sum += stack.peek();
            if (input.substring(st, ed).contains("."))
                maxv = Math.max(maxv, sum + stack.size() - 1);
            st = ed + 1;
        }
        return maxv;
    }
}

单调栈

单调栈只是一种结果的表现形式

怎么想到使用单调栈呢？如何给单调栈定义呢？

有点类似二分。

找到第一个和当前数不一样的数字。

形象地来说，找到第一个某一方面比当前角色强/弱的角色

单调栈中的栈首就是这个角色。

整个栈都满足这一性质，但栈首是最接近不满足的。

普通单调栈每日温度

class Solution {
    public int[] dailyTemperatures(int[] t) {
        /**
            单调栈 反向第一个>当前数的下标
         */
        int[] res = new int[t.length];
        Stack<Integer> stack = new Stack<>();
        for (int i = t.length - 1; i >= 0; i --){
            while (!stack.isEmpty() && t[stack.peek()] <= t[i]) stack.pop();
            if (!stack.isEmpty()) res[i] = stack.peek() - i;
            stack.push(i);
        }
        return res;
    }
}

特殊意义单调栈456. 132 模式

o(n^3)暴搜的方法，超时

class Solution {
    public boolean find132pattern(int[] nums) {
        int n = nums.length;
        boolean flag = false;
        for (int i = 0; i < n; i ++){
            for (int j = i + 1; j < n; j++){
                int k = j + 1;
                while (k < n){
                   if (nums[i] < nums[k] && nums[k] < nums[j]) {
                        flag = true; return flag;
                    } 
                    k++;
                }
            }
        }
        return flag;
    }
}

单调栈思路o (n)

对于每个numi 找到numk,其中numk满足这样一个性质：

存在j < k，有 numj > numk

我们只要遍历每个i，找到对于numi来说，最满足性质的numk（我们使用right来存放）即可

那么我们怎么来求这个right呢？

这里有一个性质

我们从后向前遍历(保证单调递减栈中元素的下标单调递减)，把所有不满足性质的numk存入栈中，最终栈是单调的

假设这个性质成立

栈 - 图1

最后再把numi存入栈，保证每次操作存入的数都是递减的，这样整体栈单调递减

class Solution {
    public boolean find132pattern(int[] nums) {
        Stack<Integer> s = new Stack<Integer>();
        int right = Integer.MIN_VALUE;
        for (int i = nums.length - 1; i >= 0; i --){
            if (nums[i] < right) return true;
            while (!s.isEmpty() && nums[i] > s.peek()){
                right = Math.max(s.peek(), right);
                s.pop();
            }
            s.push(nums[i]);
        }
        return false;
    }
}

典型单调栈 + 循环数组503. 下一个更大元素 II

思路

这是一个典型的单调栈问题，我们只需要开两倍数组就可以了

要注意我将答案覆盖到原数组，因此需要将原数组的元素保存一下

class Solution {
    public int[] nextGreaterElements(int[] nums) {
        //典型的单调栈问题,不过增加了一个循环数组
        //对于循环数组来说，我们在区间dp中遇到过，开两倍的空间就可以了
        Stack<Integer> s = new Stack<Integer>();
        int n = nums.length;
        if (n == 0) return nums;
        int[] nums2 = new int[2 * n];
        int[] res = new int[n];
        for (int i = 0; i < n; i++){
            nums2[i] = nums[i];
            nums2[i + n] = nums[i];
        }
        for (int i = 2 * n - 1; i >= 0; i--){
            while (!s.isEmpty() && s.peek() <= nums2[i]) s.pop();
            int tmp = nums2[i];
            if (s.isEmpty()) nums2[i] = -1;
            else nums2[i] = s.peek();
            s.push(tmp);
        }
        for (int i = 0; i < n; i ++) res[i] = nums2[i];
        return res;
    }
}

栈中数据的意义 42. 栈的压入、弹出序列

我的思路

压入序列T，弹出序列S，当前数为t、s

将t压入栈，对当前栈顶元素t进行判断

如果 t == s，将t弹出栈，两个序列都遍历下一个数
否则T遍历下一个数

将后一个数t压入栈，循环操作

如果遍历结束

正确思路

将t压入栈，循环当前栈顶元素t进行判断
- 如果 t == s，将t弹出栈， S序列遍历下一个数
遍历结束后，如果栈为空代表匹配，否则不匹配

能看出来，差别就是t、s判断的时候，我没有添加循环判断。循环判断保证当前序列的一致性，因此需要循环判断

本质上是对栈的认知不够，当t压入栈中，栈中存放的是t为首的弹出序列。因此要循环整个栈。

class Solution {
    public boolean isPopOrder(int [] pushV,int [] popV) {
        Stack<Integer> s = new Stack<Integer>();
        int l1 = pushV.length, l2 = popV.length;
        if (l1 == 0 && l2 == 0) return true;
        if (l1 != l2) return false;

        for (int i = 0, j = 0; i < l1; i++){
            s.push(pushV[i]);
            while (s.size() > 0 && s.peek() == popV[j]) {
                s.pop();
                j ++; 
            }
        }
        if (s.size() == 0) return true;
        else return false;
    }
}

特殊单调栈42. 接雨水 - 力扣

class Solution {
    public int trap(int[] height) {
        //单调栈，每次先判断当前height[i] > height[stack.peek()]
        //如果stack的第二个栈顶left还存在，说明可能形成凹槽，计算宽度 i - left -1
        // 高度 min(h[i], h[left]) - h[peek]
        //计算完之后相当于把坑填平了，
        //peek pop出去,接着把i存入栈中
        int num = height.length;
        if (num == 0) return 0;
        Stack<Integer> s = new Stack<>();
        s.push(0); int res = 0;
        for (int i = 1; i < num; i ++){
            while (s.size() > 1 && height[i] > height[s.peek()]){
                int bottom = s.pop(), left = s.peek();
                int width = i - left - 1, h = Math.min(height[i], height[left]) - height[bottom];
                if (width > 0 && h > 0)
                    res += width * h; 
            }
            s.push(i);
        }
        return res;
    }
}

栈