辅助栈和栈应用问题解析

1.括号匹配问题

栈的典型题目还是非常明显的,括号匹配、表达式计算等等几乎都少不了栈,本小节我们就看两个最经典的问题。
首先看题目要求,LeetCode20. 给定一个只包括 '(',')','{','}','[',']' 的字符串 s ,判断字符串是否有效。有效字符串需满足:

1.左括号必须用相同类型的右括号闭合。

2.左括号必须以正确的顺序闭合。

3.每个右括号都有一个对应的相同类型的左括号。

示例1:
输入:s = "()[]{}"
输出:true

本题要求做括号必须与正确顺序闭合,因此先想到顺序并且特殊先后顺序的数据结构:栈

class Solution {
    public boolean isValid(String s) {
        if (s.length() <= 1) {
            return false;
        }
        Map<Character, Character> smap = new HashMap<>();
        smap.put('(', ')');
        smap.put('{', '}');
        smap.put('[', ']');

        Stack<Character> stack = new Stack<>();


        for (char c:s.toCharArray()) {
            if(smap.containsKey(c)){
                stack.push(c);
            }else {
            if(stack.isEmpty()){
                return false;
            }
                if(smap.get(stack.pop())!=c){
                    return false;
                }
            }
          
    }  return stack.isEmpty();
}
}

这里需要注意的一点:栈已经为空时,说明右括号数量大于左括号因此返回false,还有一点注意的是,这里的map的作用,仅仅只是为了将左右括号的方便获取

2.最小栈

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

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

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

因此可以借助辅助栈

时刻有一个辅助栈记录当前的最小值,两个需要注意的细节:

1.pop时记得将辅助栈的元素删除

2.辅助栈需要提前存入一个特殊值,否则栈中不存在元素时会空指针异常

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);
    val = val<minStack.peek()?val : minStack.peek();
    minStack.push(val);
}
public int pop(){
    minStack.pop();
    return xStack.pop();
}
public int getMin(){
    return minStack.peek();
}
public int top(){
    return xStack.peek();
}


}

问:如果不借助额外内存空间,怎么解决?

这种方法的话,我们的 stack 栈中,不能存放原始数值,而是应该存放 差值,啥差值?就是存放栈顶最小值的差值。我还是详细一点给大家讲一个案例吧,案例配合代码,应该还是挺好理解的,例如 arr = {2, 1, 3, 0},那么把这些元素入栈时,stack 栈中元素以及最小值的变化如下

整体来说就是通过数学的运算求出了每次栈的值

当新加元素小于当前栈最小值时:此时最小值一定是新加的元素,需要更新min的值

大于时,只需要将新增的元素减去当前的最小值就能得到,需要得到值时,只需将当前min值与对应栈当前的值的绝对值相加就行

image-20231012003403859

class MinStack {

    Deque<Long> minStack;
    long min;

    public MinStack(){
    minStack = new LinkedList<>();
}
    public void push(int val){
    if(minStack.isEmpty()){
        min = val;
        minStack.push(0L);
    }else{
        long compare = val - min; 
        minStack.push(compare);
        min = compare<0? val:min;
    }
    
}
 
 public void pop(){
     long top = minStack.peek();
     if(top<0){
         min = min - top;
     }
     minStack.pop();
 }

 public int getMin(){
     return (int)min;
 }
    
public int top() {
        long peek = minStack.peek();
        // 若当前栈顶小于等于0,说明最小值就是栈顶元素
        if(peek<=0) return (int)min;
        // 否则就是min+peek
        return (int)(min+peek);
    }
}


这道题这种解法需要有几点注意:

1.当题目没有限制数值范围时候,需要防止数值溢出,可以用long代替int解决

2.第一次push时,需要将min设为第一个元素,防止忘记

3.最大栈

类似最小栈,但是需要注意的是popMax,这里借助了一个栈将最大值弹出后,再次推回

class MaxStack {
    Stack<Integer> stack;
    Stack<Integer> maxStack;

    public MaxStack() {
        stack = new Stack();
        maxStack = new Stack();
        stack.push(Integer.MIN_VALUE);
    }

    public void push(int x) {
        int max = stack.peek()< x ?x :stack.peek() ;
        maxStack.push(x);
        stack.push(max);
    }

    public int pop() {
        stack.pop();
       return maxStack.pop();
    }

    public int top() {
        return maxStack.peek();
    }

    public int peekMax() {
        return stack.peek();
    }

    public int popMax() {

        Stack<Integer> buffer = new Stack<>();
        int max = peekMax();
        while (top()!=max){
            buffer.push(pop());
        }
        pop();
        while (!buffer.isEmpty()){
            push(buffer.pop());
        }
        return max;
    }