精解括号匹配问题与极致栈设计：揭开最大栈和最小栈的奥秘

深藏阁楼爱情的钟 2024-02-19 10:08 29阅读 0赞

#### 目录 ####

*   *  括号匹配问题
     *  最小栈
     *  最大栈

最大栈和最小栈是极致栈的两个重要变种。最大栈用于存储当前匹配的最大值，而最小栈用于存储当前匹配的最小值。

### 括号匹配问题 ###

这个问题我们来看力扣20题的描述：  
给定一个只包括 ‘(’，‘)’，‘\{’，‘\}’，‘\[’，‘\]’ 的字符串 s ，判断字符串是否有效。

有效字符串需满足：

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

> 示例 1：  
> 输入：s = “()”  
> 输出：true  
> 示例 2：  
> 输入：s = “()\[\]\{\}”  
> 输出：true  
> 示例 3：  
> 输入：s = “(\]”  
> 输出：false

对于这个题我们有两种解决思路：  
1.我们用哈希表把所有符号先存储起来，左边符号作key，右边符号作value。遍历字符串的时候，遇见左边符号就入栈，遇见右边符号就与栈顶的符号进行比较，不匹配就返回false。

public boolean isValid(String s) {
        
            //获取字符串长度
            int n = s.length();
            //如果字符串长度为奇数，则返回false
            if (n % 2 == 1) {
        
                return false;
            }
            //创建一个HashMap，用于存储字符串中的括号
            Map<Character, Character> map = new HashMap<>();
            map.put('[', ']');
            map.put('(', ')');
            map.put('{', '}');
            //创建一个栈，用于存储字符串中的括号
            Stack<Character> stack = new Stack<>();
            //遍历字符串中的每一个字符
            for (int i = 0; i < s.length(); i++) {
        
                char item = s.charAt(i);
                //如果字符串中的字符在HashMap中存在，则将其压入栈中
                if (map.containsKey(item)) {
        
                    stack.push(item);
                } else {
        
                    //如果栈不为空，则弹出栈顶元素，如果弹出的元素与当前字符串中的字符不匹配，则返回false
                    if (stack.isEmpty() == false) {
        
                        char pop = stack.pop();
                        if (map.get(pop) != item) {
        
                            return false;
                        }
                    } else {
        
                        return false;
                    }
    
                }
    
            }
            //如果栈为空，则返回true，否则返回false
            return stack.isEmpty();
        }

1.  单纯的使用栈，如果遇见左边符号直接压入栈中，遇见右边的符号是先判断栈是否为空，为空则返回false，不为空则弹出栈顶元素，如栈顶元素不为相匹配的左边符号则直接返回false，最后元素遍历完返回栈是否为空。

public boolean isValid(String s) {
        
            int n = s.length();
            // 如果字符串长度为奇数，则直接返回false
            if (n % 2 == 1) {
        
                return false;
            }
            // 创建一个栈
            Deque<Character> stack = new LinkedList<>();
            // 遍历字符串
            for (int i = 0; i < s.length(); i++) {
        
                char c = s.charAt(i);
                // 如果当前字符为左括号，则将其压入栈中
                if (c == '(' | c == '[' || c == '{') {
        
                    stack.push(c);
                // 如果当前字符为右括号，则从栈中弹出一个元素，如果弹出的元素与当前字符不匹配，则返回false
                } else if (c == '}' || c == ']' || c == ')') {
        
                    if (stack.isEmpty()) {
        
                        return false;
                    }
                    char top = stack.pop();
                    if ((top != '(' && c == ')') || (top != '{' && c == '}') || (top != '[' && c == ']')) {
        
                        return false;
                    }
                }
    
            }
            // 如果栈为空，则返回true，否则返回false
            return stack.isEmpty();
        }

### 最小栈 ###

我们来看力扣155题的描述：  
设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。

实现 MinStack 类:

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

这个题通俗的理解就是给栈提供一个能获取最小元素的方法并且要在常数时间内。  
我们可以设计一个辅助栈，与元素栈同步插入与删除，用于存储每个元素入栈时的最小值（也就是说在辅助栈中我们每次插入的是元素栈中的最小值）  
![在这里插入图片描述][28bf9cae93f240ec9de7ae5dcd7b3801.png]

*  当一个元素要入栈时，我们取当前辅助栈的栈顶存储的最小值，与当前要入栈的元素中的最小值插入辅助栈中。
 *  当一个元素要出栈时，我们把辅助栈的栈顶元素也一并弹出。  
    我们来看具体实现代码：

class MinStack {
        
        // 定义两个双端队列，分别存放输入的值和当前的最小值
        Deque<Integer> xStack;
        Deque<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(minStack.peek(), val));
        }
    
        public void pop() {
        
            // 弹出双端队列的最后一个值
            xStack.pop();
            minStack.pop();
        }
    
        public int top() {
        
            // 返回双端队列的最后一个值
            return xStack.peek();
        }
    
        public int getMin() {
        
            // 返回双端队列的最小值
            return minStack.peek();
        }
    }

### 最大栈 ###

跟最小栈实现方法类似寻找最大值。  
需要注意的就是最后一个方法，弹出最大值，具体就是拿到最大元素，然后在数字栈中把最大值以上的元素全部弹出存储在新建的栈中，然后弹出最大值，最后把新建的栈中的元素重新压入数字栈中。  
由于力扣最大栈是VIP题目，我们可以尝试一下牛客的[最大栈问题][Link 1]。

class MaxStack {
        
        // 定义两个栈，一个用来存储数字，另一个用来存储最大值
        Deque<Integer> xStack;
        Deque<Integer> maxStack;
    
        public MaxStack() {
        
            // 初始化两个栈
            xStack = new LinkedList<>();
            maxStack = new LinkedList<>();
    
        }
    
        public void push(int val) {
        
            // 获取当前最大值，如果栈为空，则最大值为当前值
            int max = maxStack.isEmpty() ? val : maxStack.peek();
            // 比较当前值和最大值，取最大值
            max = max > val ? max : val;
            // 将值和最大值分别压入栈中
            xStack.push(val);
            maxStack.push(max);
        }
    
        public int pop() {
        
    
            // 弹出最大值栈顶元素
            maxStack.pop();
            // 弹出数字栈顶元素
            return xStack.pop();
        }
    
        public int top() {
        
            // 返回数字栈顶元素
            return xStack.peek();
        }
    
        public int peekMax() {
        
            // 返回最大值栈顶元素
            return maxStack.peek();
        }
    
        public int popMax() {
        
            // 获取最大值栈顶元素
            int max = peekMax();
            // 创建一个栈
            Stack<Integer> stack = new Stack<>();
            // 当栈顶元素不等于最大值时，将栈顶元素压入栈中
            while (top() != max) {
        
                stack.push(pop());
            }
            // 弹出数字栈顶元素
            pop();
            // 将栈中的元素弹出，压入数字栈中
            while (!stack.isEmpty()) {
        
                push(stack.pop());
            }
            // 返回最大值
            return max;
        }
    
    }

[28bf9cae93f240ec9de7ae5dcd7b3801.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/19/7b9867148e204ea58e728bb58da80fcc.png
[Link 1]: https://www.nowcoder.com/questionTerminal/54da2151c9b047b38100ce3f58635a76