第 4 关 | 站不住的栈：2.白银挑战 —— 最大栈、最小栈、括号匹配问题解决-灵析社区

1. 括号匹配问题

栈的典型题目还是比较明显的，括号匹配，表达式计算等等都离不开栈，本小节就针对两个经典的问题进行解析。

首先看题目要求，LeetCode 20.给定一个只包含'(',')','{','}','[',']' 的字符串 s，判断字符串是否有效。有效的字符串满足：

1. 左括号必须用相同类型的右括号闭合。
2. 左括号必须以正确的顺序闭合。
3. 每个右括号都有一个对应的相同类型的左括号。

示例 1：
输入：s = "()" 输出：true 
示例 2：
输入：s = "()[]{}" 输出：true 
示例 3：
输入：s = "(]" 输出：false

本题比较麻烦的点在于如何判断两个符号是不是同一组得，我们可以将哈希表将所有的符号进行存储，左半边做 key，右半边做 value，遍历字符串的时候，遇到左半边的符号就入栈，遇到右半边的符号就和栈顶的符号比较，不匹配就返回 false（题目没有使用哈希表，因为我个人感觉直接匹配可能更快）

class Solution {
    public boolean isValid(String s) {
        if(s.length() <= 1){
            return false;
        }
         Stack<Character> stack = new Stack<>();

         for(int i = 0; i < s.length();i++){
            char item = s.charAt(i);
            if( item == '(' || item == '[' || item =='{'){
                stack.push(item);
            }else{
                if(stack.size() == 0){
                    return false;
                }
                char left = stack.pop();
                if((left == '{' && item == '}' )
                || (left == '[' && item == ']') 
                || (left == '(' && item == ')')){
                    continue;
                }else{
                    return false;
                }
            }
         }
         return stack.size() == 0;
    }
}

LeetCode 给我们赵乐十几个括号匹配的问题，都是条件变去，但是解决起来有难有易，如果感兴趣的话可以继续研究一下：

• LeetCode 20.有效的括号
• LeetCode 22 括号生成
• LeetCode 32 最长有效括号
• LeetCode 301 删除无效的括号
• LeetCode 856 括号的分数

2. 最小栈

LeetCode 155 ，设计一个支持push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。

实现 MinStack 类:

• MinStack() 初始化堆栈对象。
• void push(int val) 将元素val推入堆栈。
• void pop() 删除堆栈顶部的元素。
• int top() 获取堆栈顶部的元素。
• int getMin() 获取堆栈中的最小元素。

示例 1:

输入：
["MinStack","push","push","push","getMin","pop","top","getMin"]
[[],[-2],[0],[-3],[],[],[],[]]

输出：
[null,null,null,null,-3,null,0,-2]

解释：
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin();   --> 返回 -3.
minStack.pop();
minStack.top();      --> 返回 0.
minStack.getMin();   --> 返回 -2.

本题的关键在于理解 getMin（） 到底表示什么，可以看一个例子上面的示例画成示意图如下：

这里的关键在于理解对应的 Min 栈内，中间元素为什么是 -2 ，理解了本题就非常简单了。

题目要求在常数时间内获取栈的最小值，因此不能在 getMin ( )的时候再去计算最小值，最好应该在 push 或者 pop 的时候就已经计算机好了当前栈中的最小值。

对于栈来说，如果一个元素 a 在入栈的时候，栈里面有其他的元素 b，c，d，那么无论这个栈在之后经历了什么操作，只要在栈 a 中，b,c,d就一定在栈中，因为 a 被弹出之前，b，c，d 不会被弹出。

因此，在操作过程中的任意一个时刻，只要栈顶的元素是 a，那么我们就可以确定栈里面现在的元素一定是 a，b,c,d.那么，我们可以在每个元素 a 入栈的时候就把当前栈的最小值 m 存储起来，然后在这之后，无论什么时候，如果栈顶元素是 a，那么我们就可以返回最小值 m 。

按照上面的思路，我们只需要设计一个数据结构，使得每个元素 a 与其相应的最小值 m 时刻保持一一对应。因此我们可以使用一个辅助栈，与元素栈同步插入和删除，用于存储于每个元素对应的最小值。

• 当一个元素要入栈的时候，我们取当前辅助栈的栈顶存储的最小值，与当前元素比较得出最小值，将这个最小值插入辅助栈中；
• 当一个元素要出栈的时候，我们把辅助栈的栈顶元素也一并弹出；

在任意一个时刻，栈内元素的最小值就存储在辅助栈的栈顶元素中。

class MinStack {
    Deque<Integer> xStack;
    Deque<Integer> minStack;

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

在以上方法之后，我进行了一部分的改进，使用链栈实现最小栈查询，这样的话可以提高效率

class MinStack {
     /**
     * 私有化头结点
     */
    private  Node head;

    public MinStack() {

    }

    /**
     * '
     * 入栈
     *
     * @param val 插入的值
     */
    public void push(int val) {
        if (head == null){
            head = new Node(val,val,null);
            return;
        }
        head = new Node(val,Math.min(val,head.min),head);
    }

    /**
     * 出栈
     */
    public void pop() {
        head = head.next;
    }

    /**
     * 查看栈顶元素
     *
     * @return
     */
    public int top() {
        return head.val;
    }

    /**
     * 获取栈中元素最小值
     *
     * @return 最小值
     */
    public int getMin() {
        return head.min;
    }

    /**
     * 构造化节点类，用于实现链栈
     */
    private class Node {
        private int val;
        private int min;
        private Node next;


        public Node(int val, int min, Node next) {
            this.val = val;
            this.min = min;
            this.next = next;
        }

        public Node(int val, int min) {
            this(val, min, null);
        }
    }
}

/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack obj = new MinStack();
 * obj.push(val);
 * obj.pop();
 * int param_3 = obj.top();
 * int param_4 = obj.getMin();
 */

3. 最大栈