monotonic_stack

Monotonic Stack选编

通常是一维数组，要寻找任一个元素的右边或者左边第一个比自己大或者小的元素的位置，此时就要想到可以用单调栈了。

时间复杂度为O(n)。

单调栈的本质是空间换时间，因为在遍历的过程中需要用一个栈来记录右边第一个比当前元素大/小的元素，优点是只需要遍历一次。

在使用单调栈的时候首先要明确如下几点：

1. 单调栈里存放的元素是什么？

单调栈里只需要存放元素的下标i就可以了，如果需要使用对应的元素，直接T[i]就可以获取。

1. 单调栈里元素是递增呢？ 还是递减呢？

注意一下顺序为 从栈顶到栈底的顺序

使用单调栈主要有三个判断条件。

• 当前遍历的元素T[i]小于栈顶元素T[st.top()]的情况
• 当前遍历的元素T[i]等于栈顶元素T[st.top()]的情况
• 当前遍历的元素T[i]大于栈顶元素T[st.top()]的情况

经典模板：

vector<int> nextGreaterElement(vector<int>& nums) {
    vector<int> res(nums.size()); // 存放答案的数组
    stack<int> s;
    // 倒着往栈里放
    for (int i = nums.size() - 1; i >= 0; i--) {
        // 判定个子高矮
        while (!s.empty() && s.top() <= nums[i]) {
            // 矮个起开，反正也被挡着了。。。can never be the "next great number"!
            s.pop();
        }
        // nums[i] 身后的 next great number
        res[i] = s.empty() ? -1 : s.top();
        s.push(nums[i]);
    }
    return res;
}

1. for 循环要从后往前扫描元素，因为我们借助的是栈的结构，倒着入栈，其实是正着出栈。while 循环是把两个「个子高」元素之间的元素排除，因为他们的存在没有意义，前面挡着个「更高」的元素，所以他们不可能被作为后续进来的元素的 Next Great Number 了。
2. 分析它的时间复杂度，要从整体来看：总共有 n 个元素，每个元素都被 push 入栈了一次，而最多会被 pop 一次，没有任何冗余操作。所以总的计算规模是和元素规模 n 成正比的，也就是 O(n) 的复杂度。

739. Daily Temperatures

单调栈图解详见：

https://programmercarl.com/0739.%E6%AF%8F%E6%97%A5%E6%B8%A9%E5%BA%A6.html#%E6%80%9D%E8%B7%AF

public int[] dailyTemperatures(int[] temperatures) {
    //monotonic stack
    //find the next greater element
    int[] res=new int[temperatures.length];
    Deque<Integer> stack=new LinkedList<>();
    for (int i = temperatures.length - 1; i >= 0; i--) {
        while(!stack.isEmpty() && temperatures[stack.peek()]<=temperatures[i]){
            stack.pop();
        }
        res[i]=stack.peek()==null ? 0 : stack.peek()-i;
        stack.push(i);
    }
    return res;
}

496. Next Greater Element I

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

503. Next Greater Element II

circular integer array nums

对于循环数组：考虑用mod运算模拟在nums后再加一个nums

public class LeetCode503 {
    public int[] nextGreaterElements(int[] nums) {
        Deque<Integer> stack=new LinkedList<>();
        int[] res=new int[nums.length];
        for (int i = 2*(nums.length - 1)+1; i >= 0; i--) {
            while(!stack.isEmpty() && stack.peek()<=nums[i%nums.length]){
                stack.pop();
            }
            res[i%nums.length]=stack.isEmpty() ? -1 : stack.peek();
            stack.push(nums[i%nums.length]);
        }
        return res;
    }
}

84. Largest Rectangle in Histogram

我们归纳一下枚举「高」的方法：

首先我们枚举某一根柱子 i 作为高 h=heights[i]；

随后我们需要进行向左右两边扩展，使得扩展到的柱子的高度均不小于 h。换句话说，我们需要找到左右两侧最近的高度小于 h 的柱子，这样这两根柱子之间（不包括其本身）的所有柱子高度均不小于 h，并且就是 i 能够扩展到的最远范围。

笨方法：用两个单调栈

public class LeetCode84 {
    public int largestRectangleArea(int[] heights) {
        Deque<Integer> stack=new LinkedList<>();
        int[] right=new int[heights.length]; //记录右边第一个比它小的 不存在则存入length
        int[] left=new int[heights.length]; //记录左边第一个比它小的  不存在则存入-1
        for (int i = heights.length - 1; i >= 0; i--) {
            while(!stack.isEmpty() && heights[stack.peek()]>=heights[i]){
                stack.pop();
            }
            right[i]=stack.isEmpty() ? heights.length : stack.peek();
            stack.push(i);
        }
        stack=new LinkedList<>();
        for (int i = 0; i < heights.length; i++) {
            while(!stack.isEmpty() && heights[stack.peek()]>=heights[i]){
                stack.pop();
            }
            left[i]=stack.isEmpty() ? -1 : stack.peek();
            stack.push(i);
        }

        int res=Integer.MIN_VALUE;
        for (int i = 0; i < heights.length; i++) {
            int r=right[i];
            int l=left[i];
            int area=(r-l-1)*heights[i];
            res=Math.max(res,area);
        }
        return res;
    }
}

42. Trapping Rain Water

法一：单调栈

法二：双指针+dp优化

largest rectangle area是要找一根柱子的左右两边的next greater element

trapping rain water是要找一根柱子的左右两边的greastet element，并加以判断：若两边的greatest element都比这根柱子高，则可以在这根柱子上蓄水

public int trap(int[] height) {

    int[] maxLeft=new int[height.length];
    int[] maxRight=new int[height.length];
    for (int i = 1; i < maxLeft.length-1; i++) {
        maxLeft[i]=Math.max(maxLeft[i-1],height[i-1]);
    }
    for (int i = maxRight.length - 2; i > 0; i--) {
        maxRight[i]=Math.max(maxRight[i+1],height[i+1]);
    }

    int start=1;
    int end= height.length-2;
    int res=0;
    for(int i=start; i<=end; i++){
        int left=maxLeft[i];
        int right=maxRight[i];
        if(left<=height[i] || right<=height[i]){
            continue;
        }
        int h=Math.min(left,right)-height[i];
        res+=h;
    }
    return res;
}

85. Maximal Rectangle

就是largest rectangle area的应用

把矩阵的每一行看成一个底面，迭代计算每一行的largest recatangle area

public class LeetCode85 {
    public int maximalRectangle(char[][] matrix) {
        int row=matrix.length;
        int col=matrix[0].length;
        int[] dp=new int[col];
        int max=Integer.MIN_VALUE;
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                dp[j]=matrix[i][j]=='0' ? 0 : dp[j]+1;
            }
            max=Math.max(max,largestArea(dp));
        }
        return max;
    }

    int largestArea(int[] dp){
        //largest rectangle
        //monotonic stack
        //next "greater" element, in this case, next smaller element
        int n=dp.length;
        Deque<Integer> stack=new LinkedList<>();
        int[] rightSmall=new int[n];
        for (int i = n - 1; i >= 0; i--) {
            while(!stack.isEmpty() && dp[stack.peek()]>=dp[i]){
                stack.pop();
            }
            rightSmall[i]=stack.isEmpty() ? n : stack.peek();
            stack.push(i);
        }
        stack=new LinkedList<>();
        int[] leftSmall=new int[n];
        for (int i = 0; i < n; i++) {
            while(!stack.isEmpty() && dp[stack.peek()]>=dp[i]){
                stack.pop();
            }
            leftSmall[i]=stack.isEmpty() ? -1 : stack.peek();
            stack.push(i);
        }
        int max=Integer.MIN_VALUE;
        for (int i = 0; i < n; i++) {
            int height=dp[i];
            int area=height*(rightSmall[i]-leftSmall[i]-1);
            max=Integer.max(max,area);
        }
        return max;
    }
}

456. 132 Pattern

//9 11 8 9 10 7 9
//   4  12  11  10  2 1
public boolean find132pattern(int[] nums) {
    int n=nums.length;
    Deque<Integer> stack=new LinkedList<>();
    int two=Integer.MIN_VALUE;
    for (int i = n-1; i >= 0; i--) {
        if(nums[i]<two){
            return true;
        }
        while(!stack.isEmpty() && stack.peek()<nums[i]){
            two=stack.pop();
        }
        stack.push(nums[i]);
    }
    return false;
}

907. Sum of Subarray Minimums

注意：

• 需考虑每个元素，因此 right 范围为 [0,n]
• 每当栈顶元素不能维持处于谷底，则出栈并计算

public int sumSubarrayMins(int[] arr) {
    int n=arr.length;
    int mod=(int)1e9+7;
    Deque<Integer> stack=new LinkedList<>();
    int res=0;
    for (int i = 0; i <= n; i++) {
        int curVal=i==n ? 0 : arr[i];
        while(!stack.isEmpty() && arr[stack.peek()]>curVal){
            int mid=stack.pop();
            int l=stack.isEmpty() ? -1 : stack.peek();
            long count=(mid-l)*(i-mid)%mod;
            long p=arr[mid]*count%mod;
            res+=p;
            res%=mod;
        }
        stack.push(i);
    }
    return res;
}

2104. Sum of Subarray Ranges

public long subArrayRanges(int[] nums) {
    long res=0;
    int n=nums.length;
    Deque<Integer> stack=new LinkedList<>();
    for (int i = 0; i <= n; i++) {
        int curVal= i==n ? Integer.MIN_VALUE : nums[i];
        while(!stack.isEmpty() && nums[stack.peek()]>curVal){
            int mid=stack.pop();
            int l=stack.isEmpty() ? -1 : stack.peek();
            res-=(long)(mid-l)*(i-mid)*nums[mid];
        }
        stack.push(i);
    }
    stack.clear();
    for (int i = 0; i <= n; i++) {
        int curVal= i==n ? Integer.MAX_VALUE : nums[i];
        while(!stack.isEmpty() && nums[stack.peek()]<curVal){
            int mid=stack.pop();
            int l=stack.isEmpty() ? -1 : stack.peek();
            res+=(long)(mid-l)*(i-mid)*nums[mid];
        }
        stack.push(i);
    }
    return res;
}

1130. Minimum Cost Tree From Leaf Values

public int mctFromLeafValues(int[] arr) {
    Deque<Integer> stack=new LinkedList<>();
    stack.push(Integer.MAX_VALUE);
    int res=0;
    for (int num : arr) {
        while(stack.peek()<=num){
            //left          mid        right
            //stack.peek() stack.pop() num
            int mid=stack.pop();
            res+=mid*Math.min(stack.peek(),num);
        }
        stack.push(num);
    }
    while(stack.size()>2){
        res+=stack.pop()*stack.peek();
    }
    return res;
}

1475. Final Prices With a Special Discount in a Shop

public int[] finalPrices(int[] prices) {
    //next smaller or equal element
    int n=prices.length;
    int[] res=new int[n];
    Deque<Integer> stack=new LinkedList<>();
    for (int i = n-1; i >= 0; i--) {
        int cur=prices[i];
        while(!stack.isEmpty() && stack.peek()>cur){
            stack.pop();
        }
        int dis=stack.isEmpty() ? 0 : stack.peek();
        res[i]=cur-dis;
        stack.push(cur);
    }
    return res;
}

1673. Find the Most Competitive Subsequence

If the element is greater than the dequeue’s kth element, we don’t need to store it. This also slightly improves performance while removing from the dequeue, as we didn’t add unnecessary elements.

public int[] mostCompetitive(int[] nums, int k) {
    Deque<Integer> stack=new LinkedList<>();
    int n=nums.length;
    int[] res=new int[k];
    for (int i = 0; i < n; i++) {
        //make sure after deleting, there is >= k elements
        while(!stack.isEmpty() &&stack.size()+n-i>k && stack.peek()>nums[i]){
            stack.pop();
        }
        if(stack.size()<k){
            stack.push(nums[i]);
        }
    }
    int idx=k-1;
    while(idx>=0){
        res[idx--]=stack.pop();
    }
    return res;
}

1776. Car Fleet II

https://leetcode.com/problems/car-fleet-ii/discuss/1105620/Java-oror-clean-O(n)-Monotonic-Stack-Solution-oror-Detailed-Explanations

public double[] getCollisionTimes(int[][] cars) {
    int n=cars.length;
    double[] res=new double[n];
    Arrays.fill(res,-1.0);
    Deque<Integer> stack=new LinkedList<>();
    for (int i = n-1; i >= 0; i--) {
        int[] car=cars[i];
        int pos=car[0];
        int speed=car[1];
        while(!stack.isEmpty()){
            int j=stack.peek();
            int[] car2=cars[j];
            int pos2=car2[0];
            int speed2=car2[1];
            double time=(double)(pos2-pos)/(speed-speed2);
            if(speed>speed2 && (time<res[j]
                    || res[j]<0)){
                //1.faster
                //2.collide before car 2 vanishes, or never vanishes
                res[i]=time;
                break;
            }else{
                //car2 would never be collided by [0,car1]
                stack.pop();
            }
        }
        stack.push(i);
    }
    return res;
}

2355. Maximum Number of Books You Can Take

https://leetcode.com/problems/maximum-number-of-books-you-can-take/discuss/2508360/Java-O(n)-DP-%2B-Monotonic-Stack-oror-Beats-73-time-and-space-oror-Explanation-with-comments

Basically for any index i, j is the first index to the left of i where books[j] < books[i] - i + j. This index j is obtained using a monotonic stack.

first smaller element to the left

public long maximumBooks(int[] books) {
    Deque<Integer> stack=new LinkedList<>();
    int n=books.length;
    long res=0;
    long[] dp=new long[n];
    for (int i = 0; i < n; i++) {
        //books[i], books[i]-1, books[i]-i+j
        //i,        i-1,       j
        while(!stack.isEmpty() &&
                books[i]-i+stack.peek()<=books[stack.peek()]){
            //once valid, will be valid for all following elements
            stack.pop();
        }
        //books[i]-i+j+1,..books[i]
        dp[i]=(stack.isEmpty() ? 0 : dp[stack.peek()]) +
                sum(books[i]) -
                sum(books[i]-i+(stack.isEmpty() ? -1 : stack.peek()));
        res=Math.max(res,dp[i]);
        stack.push(i);
    }
    return res;
}

private long sum(int n){
    if(n<=0){
        return 0;
    }
    //0,1,2,...,n
    return (long)n*(long)(n+1)/2;
}