LeetCode——栈

栈

特点： 先进后出，后进先出

适合： 相当于一个暂存的地方，方便回来找

特： 单调栈——需要找到左边或者右边第一个比当前位置数大或者小的数字

数据类型

LinkedList<T> stack = new LinkedList<>();
addFirst==push;removeFirst==pop;peek
    
// 面向接口编程，封装性更好
Deque<T> stack = new ArrayDeque<>();
addLast==push;pollLast==pop;peekLast

1.有效的括号20简单

class Solution {
    public boolean isValid(String s) {
        // 使用Java中的LinkedList创建栈，遍历s，如果和栈顶元素匹配则弹出，如果不匹配则压入；遍历结束后，如果列表为空，说明字符串是有效的，反之无效
        // 注意：Java中定义集合如果集合元素是基本数据类型，要使用他们的包装类；String不是数组，没有索引
        // 改进：使用哈希map将括号存起来，不用这么多if条件
        // 1. 进行一些特殊情况的判断
        int len = s.length();
        // 如果字符串长度是奇数，说明不是有效字符串
        if (len % 2 != 0) {
            return false;
        }
        // 2. 定义栈_Java中定义集合如果集合元素是基本数据类型，要使用他们的包装类
        LinkedList<Character> stack = new LinkedList<>();
        // 3. 开始遍历字符串
        for (int i = 0; i < len; i++) {
            if (stack.size() == 0 || s.charAt(i) == '(' || s.charAt(i) == '{' || s.charAt(i) == '[') {
                stack.addFirst(s.charAt(i));
            } else {
                char temp = stack.removeFirst();
                if ((temp == '(' && s.charAt(i) == ')') || (temp == '{' && s.charAt(i) == '}') || (temp == '[' && s.charAt(i) == ']')) {
                    continue;
                } else {
                    return false;
                }
            }
        }
        if (stack.size() == 0) {
            return true;
        }
        return false;
    }
}

简单题补充：

1047删除字符串中的所有相邻重复项]

class Solution {
    public String removeDuplicates(String s) {
        // 思路：遍历字符串s，将字符串中的字符压入栈中，最后将栈中元素弹出并翻转，得到最终字符串
        // 压栈：栈为空或栈顶元素与遍历到的元素不相等
        // 出栈：栈顶元素与遍历到的元素相等
        // 1. 定义一个栈
        Deque<Character> stack = new ArrayDeque<>();
        // 2. 遍历
        for (int i = 0; i < s.length(); i++) {
            if (stack.isEmpty()) {
                stack.addLast(s.charAt(i));
                continue;
            }
            if (stack.peekLast() == s.charAt(i)) {
                stack.pollLast();
            } else {
                stack.addLast(s.charAt(i));
            }
        }
        // 3. 定义结果字符串，为了方便翻转，定义StringBuilder
        StringBuilder result = new StringBuilder();
        while (!stack.isEmpty()) {
            result.append(stack.pollLast());
        }
        return result.reverse().toString();
    }
}

150. 逆波兰表达式求值

class Solution {
    public int evalRPN(String[] tokens) {
        // 思路：定义一个栈，如果是数字压入栈中，如果是运算符，弹出两个数字，计算之后将结果压入栈中，最后遍历结束，栈中存在的最后一个值就是整个表达式的计算值
        // 注意：计算的时候弹出来的数计算要反过来！！！
        Deque<Integer> stack = new ArrayDeque<>();
        int n = tokens.length;
        for (int i = 0; i < n; i++) {
            String s = tokens[i];
            if (s.equals("+")) {
                int a = stack.pollLast();
                int b = stack.pollLast();
                stack.addLast(b + a);
                System.out.println("+" + stack.peekLast());
            } else if (s.equals("-")) {
                int a = stack.pollLast();
                int b = stack.pollLast();
                stack.addLast(b - a);
            } else if (s.equals("*")) {
                int a = stack.pollLast();
                int b = stack.pollLast();
                stack.addLast(b * a);
            } else if (s.equals("/")) {
                int a = stack.pollLast();
                int b = stack.pollLast();
                stack.addLast(b / a);
                System.out.println("/" + stack.peekLast());
            } else {

                stack.addLast(Integer.parseInt(s));
                System.out.println(stack.peekLast());
            }
        }
        return stack.pollLast();
    }
}

2.最小栈155中等

特点：辅助栈的使用

// class MinStack {
//     public int minValue;  // 记录最小值
//     public LinkedList<Integer> stack;

//     public MinStack() {
//         minValue = Integer.MAX_VALUE;
//         stack = new LinkedList<>();
//     }
    
//     public void push(int val) {
//         if (val < minValue) {
//             minValue = val;
//         }
//         stack.addFirst(val);
//     }
    
//     public void pop() {
//         int temp = stack.removeFirst();
//         // 如果没有弹出最小元素
//         if (temp != minValue) {
//             return;
//         } else {
//             // 如果弹出了最小元素
//             minValue = Integer.MAX_VALUE;
//             for (int x: stack) {
//                 if (x < minValue) {
//                     minValue = x;
//                 }
//             }
//         }
//     }
    
//     public int top() {
//         int temp = stack.removeFirst();
//         stack.addFirst(temp);
//         return temp;
//     }
    
//     public int getMin() {
//         return minValue;
//     }
// }

// 使用辅助栈，也就是最小栈里面一致存放的是当前最小值；压入新元素，最小栈比较当前最小值和当前最小元素，插入最小
class MinStack {
    LinkedList<Integer> xStack;
    LinkedList<Integer> minStack;

    public MinStack() {
        xStack = new LinkedList<>();
        minStack = new LinkedList<>();
        minStack.push(Integer.MAX_VALUE);
    }
    
    public void push(int val) {
        xStack.push(val);
        minStack.push(Math.min(val, minStack.peek()));
    }
    
    public void pop() {
        xStack.pop();
        minStack.pop();

    }
    
    public int top() {
        return xStack.peek();
    }
    
    public int getMin() {
        return minStack.peek();
    }
}

3.每日温度739中等

单调栈的直接使用！！！

// class Solution {
//     public int[] dailyTemperatures(int[] temperatures) {
//         // 思路：单调栈，如果遍历到当前元素小于栈顶元素，压栈；如果大于，不断弹出
//         LinkedList<Integer> indexStack = new LinkedList<>();
//         int len = temperatures.length;
//         int[] ans = new int[len];
//         // 遍历温度数组
//         for (int i = 0; i < len; i++) {
//             // 如果栈是空的
//             if (indexStack.isEmpty()) {
//                 indexStack.push(i);
//             } else {
//                 // 不为空，就要看栈顶元素和当前温度的大小
//                 if (temperatures[i] <= temperatures[indexStack.peek()]) {
//                     indexStack.push(i);
//                 } else {
//                     while (! indexStack.isEmpty()) {
//                         if (temperatures[i] > temperatures[indexStack.peek()]) {
//                             int temp = indexStack.pop();
//                             ans[temp] = i - temp;
//                         } else {
//                             break;
//                         }
//                     }
//                     indexStack.push(i);
//                 }
//             }
//         }
//         return ans;
//     }
// }


// 简化
class Solution {
    public int[] dailyTemperatures(int[] temperatures) {
        // 思路：单调栈，如果遍历到当前元素小于栈顶元素，压栈；如果大于，不断弹出
        LinkedList<Integer> indexStack = new LinkedList<>();
        int len = temperatures.length;
        int[] ans = new int[len];
        // 遍历温度数组
        for (int i = 0; i < len; i++) {
            while (! indexStack.isEmpty()) {
                if (temperatures[i] > temperatures[indexStack.peek()]) {
                    int temp = indexStack.pop();
                    ans[temp] = i - temp;
                } else {
                    break;
                }
            }
            indexStack.push(i);
        }
        return ans;
    }
}

4.柱状图中最大的矩形84困难

单调栈的反复使用！

class Solution {
    public int largestRectangleArea(int[] heights) {
        // 思路：遍历每根柱子，找到左右两边第一个比它矮的，面积为(右-左)*min(高度最小)
        int n = heights.length;
        // 定义左右两个数组，分别保存左边和右边第一个比该位置小的下标
        int[] l = new int[n];
        int[] r = new int[n];
        // 初始填充
        Arrays.fill(l, -1);
        Arrays.fill(r, n);
        // 定义栈——辅助寻找第一个小于的元素
        Deque<Integer> stack = new ArrayDeque<>();
        // 从头到尾遍历，找到右边第一个小于该位置的下标
        for (int i = 0; i < n; i++) {
            while (! stack.isEmpty() && heights[stack.peekLast()] > heights[i]) {
                r[stack.pollLast()] = i;
            }
            stack.addLast(i);
        }
        // 从尾遍历到头，找到左边第一个不小于该位置的小标
        stack.clear();
        for (int i = n - 1; i >= 0; i--) {
            while (!stack.isEmpty() && heights[stack.peekLast()] > heights[i]) {
                l[stack.pollLast()] = i;
            }
            stack.addLast(i);
        }
        // 开始计算面积
        int maxVal = 0;
        for (int i = 0; i < n; i++) {
            maxVal = Math.max(maxVal, heights[i] * (r[i] - l[i] - 1));
        }
        return maxVal;
    }
}

[未完待续……]

总结： 定义栈、三个栈的基本操作

? 单调栈！！加辅助空间！！