Stack

57. 20. Valid Parentheses

import org.junit.jupiter.api.Test;

import java.util.Stack;

import static org.junit.jupiter.api.Assertions.assertFalse;
import static org.junit.jupiter.api.Assertions.assertTrue;

class ValidParentheses {
    public boolean isValid(final String s) {
        final Stack<Character> stack = new Stack<>();
        for (final char c : s.toCharArray()) {
            if (c == '(' || c == '{' || c == '[') {
                stack.push(c);
            } else if (stack.isEmpty()) {
                return false;
            } else if (c == ')') {
                if (stack.pop() != '(') {
                    return false;
                }
            } else if (c == '}') {
                if (stack.pop() != '{') {
                    return false;
                }
            } else if (c == ']') {
                if (stack.pop() != '[') {
                    return false;
                }
            } else {
                return false;
            }
        }
        return stack.isEmpty();
    }

    @Test
    void givenInput1_whenCheckIfValid_thenReturnTrue() {
        final String input = "()";
        assertTrue(isValid(input));
    }

    @Test
    void givenInput2_whenCheckIfValid_thenReturnTrue() {
        final String input = "()[]{}";
        assertTrue(isValid(input));
    }

    @Test
    void givenInput3_whenCheckIfValid_thenReturnFalse() {
        final String input = "(]";
        assertFalse(isValid(input));
    }

    @Test
    void givenInput4_whenCheckIfValid_thenReturnFalse() {
        final String input = "]";
        assertFalse(isValid(input));
    }

}

58. 232. Implement Queue using Stacks

class MyQueue {
public:
    MyQueue() {
    }
    
    void push(int x) {
        pushStack.push(x);
    }
    
    int pop() {
        pushStackToPopStackIfNecessary();
        int result = popStack.top();
        popStack.pop();
        return result;
    }
    
    int peek() {
        pushStackToPopStackIfNecessary();
        return popStack.top();
    }
    
    bool empty() {
        return popStack.empty() && pushStack.empty();
    }
private: 
    stack<int> popStack, pushStack;
    void pushStackToPopStackIfNecessary() {
        if (popStack.empty()) {
            while (!pushStack.empty()) {
                popStack.push(pushStack.top());
                pushStack.pop();
            }
        }
    }    
};

59. 150. Evaluate Reverse Polish Notation

class Solution {
    public int evalRPN(String[] tokens) {
        List<String> operands = List.of("+", "-", "*", "/");
        Stack<String> stack = new Stack<>();
        for (String t : tokens) {
            if (operands.contains(t)) {
                String b = stack.pop();
                String a = stack.pop();
                if (t.equals("+")) {
                    stack.push(String.valueOf(Integer.valueOf(a) + Integer.valueOf(b)));
                } else if (t.equals("-")) {
                    stack.push(String.valueOf(Integer.valueOf(a) - Integer.valueOf(b)));
                } else if (t.equals("*")) {
                    stack.push(String.valueOf(Integer.valueOf(a) * Integer.valueOf(b)));
                } else {
                    stack.push(String.valueOf(Integer.valueOf(a) / Integer.valueOf(b)));
                }
            } else {
                stack.push(t);
            }
        }
        return Integer.valueOf(stack.pop());
    }
}

60. 155. Min Stack

class MinStack {
    private final Stack<Integer> s1 = new Stack<>();
    private final Stack<Integer> s2 = new Stack<>();

    public MinStack() {
        
    }
    
    public void push(int val) { 
        if (s1.empty() || val <= s2.peek()) {
            s2.push(val);
        }
        s1.push(val);
    }
    
    public void pop() {
        int top = s1.peek();
        if (top == s2.peek()) {
            s2.pop();
        }
        s1.pop();
    }
    
    public int top() {
        return s1.peek();
    }
    
    public int getMin() {
        return s2.peek();
    }
}

class MinStack {
private:
    stack<int> s1;
    stack<int> s2;   
public:
    MinStack() {
        
    }
    
    void push(int val) {
        if (s1.empty() || val <= s2.top()) {
            s2.push(val);
        }
        s1.push(val);
    }
    
    void pop() {
        if (s1.top() == s2.top()) {
            s2.pop();
        }
        s1.pop();
    }
    
    int top() {
        return s1.top();
    }
    
    int getMin() {
        return s2.top();
    }
};

61. 42. Trapping Rain Water

class Solution {
public:
    int trap(vector<int>& height) {
        int size = height.size();
        vector<int> left(size, 0);
        vector<int> right(size, 0);
        
        left[0] = height[0];
        for (int i = 1; i < size; i++) {
            left[i] = max(left[i-1], height[i]);
        }

        right[size-1] = height[size-1];
        for (int i = size - 2; i >= 0; i--) {
            right[i] = max(right[i+1], height[i]);
        }

        int result = 0;
        for (int i = 0; i < size; i++) {
            result += min(left[i], right[i]) - height[i];
        }
        return result;
    }
};

62. Basic Calculator

TODO

63. 84. Largest Rectangle in Histogram

class Solution {
    public int largestRectangleArea(int[] heights) {
        return stackSolution(heights);
    }

    // https://leetcode.com/problems/largest-rectangle-in-histogram/solutions/28902/5ms-o-n-java-solution-explained-beats-96/
    private int regularSolution(int[] heights) {
        if (heights == null || heights.length == 0) {
            return 0;
        }

        int[] lessFromLeft = new int[heights.length];
        int[] lessFromRight = new int[heights.length];
        lessFromLeft[0] = -1;
        lessFromRight[heights.length - 1] = heights.length;

        for (int i = 1; i < heights.length; i++) {
            int p = i - 1;
            while (p >= 0 && heights[p] >= heights[i]) {
                p = lessFromLeft[p];
            }
            lessFromLeft[i] = p;
        }

        for (int i = heights.length - 2; i >= 0; i--) {
            int p = i + 1;
            while (p < heights.length && heights[p] >= heights[i]) {
                p = lessFromRight[p];
            }
            lessFromRight[i] = p;
        }

        int maxArea = 0;
        for (int i = 0; i < heights.length; i++) {
            maxArea = Math.max(maxArea, heights[i] * (lessFromRight[i] - lessFromLeft[i] - 1));
        }

        return maxArea;
    }

    // https://leetcode.com/problems/largest-rectangle-in-histogram/solutions/995249/python-increasing-stack-explained/
    private int stackSolution(int[] heights) {
        Stack<Integer> stack = new Stack<>();
        int maxArea = 0;
        for(int i = 0; i <= heights.length; i++) {
            int height = i == heights.length ? 0 : heights[i];
            while(!stack.empty() && heights[stack.peek()] > height) {
                int h = heights[stack.pop()];
                int w = stack.empty() ? i : i - stack.peek() - 1;
                maxArea = Math.max(maxArea, h * w);
            }
            stack.push(i);
        }
        return maxArea;
    }
}