单调栈

求左边/右边第一个比当前数小的值->单调递增栈。求左边/右边第一个比当前数大的值->单调递减栈

Min Stack

• brute force solution

  • 建立两个stack, stk and minStk，两个存相同数量的数（空间不是最优）

  • 每次stk.pop()之后都call minStk.pop()

  • stk.push()的时候判断cur和minStk.peek()的大小

• improve solution

  • minStk不用每次都更新，只需要当push出现更小值的时候再push

class MinStack {
    Stack<Integer> stk, minStk;
    /** initialize your data structure here. */
    public MinStack() {
        stk = new Stack<>();
        minStk = new Stack<>();
    }
    
    public void push(int x) {
        stk.push(x);
        if (minStk.isEmpty() || minStk.peek() >= x) {
            minStk.push(x);
        }
    }
    
    public void pop() {
        int val = stk.pop();
        if (minStk.peek() == val) {
            minStk.pop();
        }
    }
    
    public int top() {
        return stk.peek();
    }
    
    public int getMin() {
        return minStk.peek();
    }
}

Max Stack

• brute force solution---Interview friendly

• 3 stacks, stk, maxStk and buffer inside of popMax()

• size of stk and maxStk is always same

class MaxStack {

    /** initialize your data structure here. */
    Stack<Integer> stk, maxStk;
    public MaxStack() {
        //brute force solution
        //3 stacks, stk, maxStk and buffer inside of popMax()
        //size of stk and maxStk is always same
        stk = new Stack<>();
        maxStk = new Stack<>();
    }
    
    public void push(int x) {
        int max = maxStk.isEmpty() ? x : maxStk.peek();
        maxStk.push(x > max ? x : max);
        stk.push(x);
    }
    
    public int pop() {
        maxStk.pop();
        return stk.pop();
    }
    
    public int top() {
        return stk.peek();
    }
    
    public int peekMax() {
        return maxStk.peek();
    }
    
    public int popMax() {
        int max = peekMax();
        Stack<Integer> buffer = new Stack<>();
        while(top() != max) {
            buffer.push(pop());
        }
        pop();
        while (!buffer.isEmpty()) {
            push(buffer.pop());
        }
        return max;
    }
}

• Optimize to not use maxStk, use a max variable instead

Largest Rectangle in Histogram

• 如何构成rectangle

• given index i, 找到i左边的第一个小于nums[i]的值，右边的第一个小于nums[i]的值

• 因此想到单调递增栈

• 每次curHeight和heights[stk.peek()]比较，如果比heights[stk.peek()]小的话，height[stk.pop()]就是height, curHeight就是右边界, 更新的栈里的stk.peek()就是左边界

class Solution {
    /*
    brute force
    2 for loops
    O(N^2) time
    
    Improved
    h = heights[stk.peek()]
    l = 左边第一个比h小的height的idx
    r = i, 左边第一个比h小的height的idx, if heights[i]< h
    w = i - l - 1
    area = h * w
    */
    public int largestRectangleArea(int[] heights) {
        if (heights == null || heights.length == 0) return 0;
        Stack<Integer> stk = new Stack<>(); //monontonic increasing stk, idx
        int max = 0;
        int n = heights.length;
        for (int i = 0; i <= n; i++) {
            int curHeight = i == n ? -1 : heights[i];
            while (!stk.isEmpty() && curHeight < heights[stk.peek()]) {
                int h = heights[stk.pop()];
                int w = stk.isEmpty() ? i : i - stk.peek() - 1;
                max = Math.max(max, h * w);
            }
            stk.push(i);
        }
        return max;
    }
}

Next greater element类问题，经典的单调栈应用

• Next greater element I

• Next greater element II

• Next greater node in Linked List

• Daily Temperature

Next Greater Element I

• 给两个数组，nums1和nums2, nums1 是nums2 的子集

• 要求返回nums1里每一个数在nums2里的next greater element

• 典型的单调栈问题

• 从右向左遍历nums2, 维护单调递减栈

• always compare nums2[i] with stk.peek()

• if nums[i] < stk.peek() then arr[i] == stk.peek()

• else stk.pop(), try again until stk.isEmpty()

• 原始版本代码

class Solution {
    /*
    从右向左遍历nums2, 维护单调递减栈
    并建立新的arr to store nextGreater element for each element in nums[i]
    always nums2[i] with stk.peek()
    if nums[i] < stk.peek() then arr[i] == stk.peek()
    else stk.pop(), try again until stk.isEmpty()
    */
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        Map<Integer, Integer> nextGreaterElements = new HashMap<>();
        Stack<Integer> minStk = new Stack<>();
        for (int i = nums2.length - 1; i >= 0; i--) {
            int num = nums2[i];
            while(!minStk.isEmpty()) {
                if(num < minStk.peek()) {
                    nextGreaterElements.put(num, minStk.peek());
                    minStk.push(num);
                    break;
                } else {
                    minStk.pop();
                }
            }
            if (minStk.isEmpty()) {
                nextGreaterElements.put(num, -1);
                minStk.push(num);
            }
        }
        int[] res = new int[nums1.length];
        for (int i = 0; i < nums1.length; i++) {
            res[i] = nextGreaterElements.get(nums1[i]);
        }
        return res;
    }
}

• 优化后的clean code

public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        Map<Integer, Integer> nextGreaterElements = new HashMap<>();
        Stack<Integer> minStk = new Stack<>();
        for (int i = nums2.length - 1; i >= 0; i--) {
            int num = nums2[i];
            while (!minStk.isEmpty() && num > minStk.peek()) {
                minStk.pop();
            }
            nextGreaterElements.put(num, minStk.isEmpty() ? -1 : minStk.peek());
            minStk.push(num);
        }
        int[] res = new int[nums1.length];
        for (int i = 0; i < nums1.length; i++) {
            res[i] = nextGreaterElements.get(nums1[i]);
        }
        return res;
    }

Next Greater Element II

• 给定一个nums, 求nums里每一个数的next greater element

• nums is circular array

• 跟第一题相同的思路，但是需要iterate 2 loops, i from 2 * n - 1 to 0

    public int[] nextGreaterElements(int[] nums) {
        int n = nums.length;
        int[] next = new int[n];
        Stack<Integer> stk = new Stack<>(); //stack, 单调递减
        for (int i = n * 2 - 1; i >= 0; i--) {
            int num = nums[i % n];
            while (!stk.isEmpty() && num >= stk.peek()) {
                stk.pop();
            }
            if (i < n) {
                next[i] = stk.isEmpty() ? -1 : stk.peek();
            }
            stk.push(num);
        }
        return next;
    }

Next Greater Node in Linked List

• 首先convert linked list to array, 然后就是典型的find next greater element的问题

• 求右边第一个比当前数大的值->单调递减栈

• follow up: 求左边第一个比当前数大的值, previous greater element 也是单调递减栈

class Solution {
    public int[] nextLargerNodes(ListNode head) {
        int[] arr = toArray(head);
        Deque<Integer> stk = new ArrayDeque<>(); //store index of arr, arr[index] descending order
        int[] res = new int[arr.length];
        for (int i = 0; i < arr.length; i++) {
            while (!stk.isEmpty() && arr[i] > arr[stk.peek()]) {
                res[stk.pop()] = arr[i];
            }
            stk.push(i);
        }
        return res;
    }
    private int[] toArray(ListNode head) {
        List<Integer> list = new ArrayList<>();
        while (head != null) {
            list.add(head.val);
            head = head.next;
        }
        int size = list.size();
        int[] arr = new int[size];
        for (int i = 0; i < size; i++) {
            arr[i] = list.get(i);
        }
        return arr;
    }
}