栈的经典算法问题

括号匹配问题

public class IsValid {

    static 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 (int i = 0; i < s.length(); i++) {
            char ch = s.charAt(i);
            if (ch == '(' || ch == '[' || ch == '{') {
                stack.push(smap.get(ch));
            } else if (stack.isEmpty() || stack.pop() != ch) {
                return false;
            }
        }
        return stack.isEmpty();
    }

    public static void main(String[] args) {
        String s = ")[]{}";
        System.out.println(isValid(s));
    }
}

最小栈

//使用两个栈，如果新放入的值比当前最小栈的栈顶值大的话，继续放入栈顶值，否则放入该值。
public class MinStack2 {
    Deque<Integer> minStack;
    Deque<Integer> stack;

    public MinStack2() {
        stack = new LinkedList<>();
        minStack = new LinkedList<>();
    }

    public void push(int val) {
        stack.push(val);
        minStack.push(Math.min(minStack.peek(), val));
    }

    public void pop() {
        stack.pop();
        minStack.pop();
    }

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

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

最大栈

//使用两个栈，如果新放入的值比当前最大栈的栈顶值小的话，继续放入栈顶值，否则放入该值。
public class MaxStack2 {

    private Deque<Integer> stack;
    private Deque<Integer> maxStack;

    public MaxStack2() {
        stack = new LinkedList<>();
        maxStack = new LinkedList<>();
    }

    public void push(int val) {
        stack.push(val);
        maxStack.push(Math.max(maxStack.peek(), val));
    }

    public void pop() {
        stack.pop();
    }

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

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