Valid Parentheses

★☆☆☆☆

Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

The brackets must close in the correct order, "()" and "()[]{}" are all valid but "(]" and "([)]" are not.

public class Solution {
    public boolean isValid(String s) {
        Stack<Character> stack = new Stack<>();
        for (int i = 0; i < s.length(); ++i) {
            if (s.charAt(i) == '(' || s.charAt(i) == '[' || s.charAt(i) == '{')
                stack.push(s.charAt(i));
            else {
                if (stack.empty()) return false;
                if (s.charAt(i) == ')') {
                    if (stack.pop() != '(') return false;
                }
                else if (s.charAt(i) == ']') {
                    if (stack.pop() != '[') return false;
                }
                else if (s.charAt(i) == '}') {
                    if (stack.pop() != '{') return false;
                }
            }
        }
        return stack.empty();
    }
}

Min Stack

★★★★☆

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.

push(x) -- Push element x onto stack. pop() -- Removes the element on top of the stack. top() -- Get the top element. getMin() -- Retrieve the minimum element in the stack.

Easy failure point:

• need to be Long, remember to cast back and forth
• store the difference between minimum value
• can't just store the value between previous minimum value, it would fail in certain case
• care for the top() function, don't always return min + popVal, since the timing you change min is after you pop()

class MinStack {
    Stack<Long> stack;
    long min;

    public MinStack() {
        stack = new Stack<Long>();
    }

    public void push(int x) {
        if (stack.isEmpty()) {
            stack.push(0L);
            min = x;
        }
        else {
            stack.push(x - min);
            if (stack.peek() < 0) min = x;
        }
    }

    public void pop() {
        if (stack.isEmpty()) return;
        long x = stack.pop();
        if (x < 0) min = min - x;
    }

    public int top() {
        return stack.peek() > 0? (int)(stack.peek() + min): (int)min; 
    }

    public int getMin() {
        return (int)(min);
    }
}