算法笔记-单调栈

单调栈

怎么能想到用单调栈呢？ 什么时候用单调栈呢？

通常是一维数组，要寻找任一个元素的右边或者左边第一个比自己大或者小的元素的位置，此时我们就要想到可以用单调栈了。时间复杂度为O(n)。

例如：要求某个元素A的右边 第一个比他大的元素，该用什么栈？
首先栈的特性在于先进后出，当元素A入栈时，他必然是后出的；
再者对于右边比这个元素A小的元素，我们一定需要入栈，因为不入栈，右边更小的元素就丢了。从这里其实就可以判断出，后进的元素一定是更小的元素；
第三点，当碰到比这个元素A更大的元素时，就已经得到了答案，A就不需要在栈内了，出栈即可，并将更大的元素入栈。

所以综上可以知道，要求某个元素A的右边 第一个比他大的元素，从栈底到栈顶应该是一个递减的序列。

每日温度

class Solution {
    public int[] dailyTemperatures(int[] temperatures) {
        Deque<Integer> s = new LinkedList<>();

        int[] res = new int[temperatures.length];

        s.push(0);
        for(int i=1;i<temperatures.length;i++){
            while(!s.isEmpty()&&temperatures[i]>temperatures[s.peek()]){
                int index = s.pop();
                res[index] = i-index;
            }
            s.push(i);
        }

        return res;
    }
}

时间O(n)
空间O(n)

下一个更大元素 I

class Solution {
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        int[] res = new int[nums1.length];

        Map<Integer,Integer> numIndex = new HashMap<>();

        for(int i=0;i<nums1.length;i++){
            numIndex.put(nums1[i],i);
            res[i] = -1;
        }

        Deque<Integer> s = new LinkedList<>();

        //单调栈，用于找某一个元素的右边第一个更大元素

        s.push(nums2[0]);

        for(int i =1;i<nums2.length;i++){
            while(!s.isEmpty()&&nums2[i]>s.peek()){
                int smaller = s.pop();
                int index = numIndex.getOrDefault(smaller,-1);
                if (index == -1){
                    continue;
                }
                res[index] = nums2[i];
            }
            s.push(nums2[i]);
        }

        return res;
    }
}

时间O(n)
空间O(n)

下一个更大元素II

class Solution {
    public int[] nextGreaterElements(int[] nums) {
        Deque<Integer> s = new LinkedList<>();

        s.push(0);
        int[]res = new int[nums.length];
        for(int i=0;i<res.length;i++){
            res[i] = -1;
        }

        //第一次遍历，用单调栈寻找线性范围内的更大元素
        for(int i=1;i<nums.length;i++){
            while(!s.isEmpty()&&nums[i]>nums[s.peek()]){
                int smallerOneIndex = s.pop();
                res[smallerOneIndex] = nums[i];
            }
            s.push(i);
        }

        if (s.isEmpty()){
            return res;
        }
        //第二次遍历，寻找循环范围内的更大元素，但是不再进栈
        for(int i=0;i<nums.length;i++){
            while(!s.isEmpty()&&nums[i]>nums[s.peek()]){
                int smallerOneIndex = s.pop();
                res[smallerOneIndex] = nums[i];
            }
        }

        return res;
    }
}

时间O(n)
空间O(n)

接雨水

按列接雨水

动态规划双数组

class Solution {
    public int trap(int[] height) {
        //按列看接雨水，每一个柱子所在处能接的雨水 是它左边***最大值***和右边***最大值*** 的较小者。

        //所以只需要求出每一个柱子对应的左侧最大值和右侧最大值即可。

        int[] leftMax = new int[height.length];
        int[] rightMax = new int[height.length];

        for(int i=1;i<height.length;i++){
            leftMax[i] = Math.max(leftMax[i-1],height[i-1]);
        }

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


        int res = 0;
        for(int i=1;i<height.length-1;i++){
            int temp =  Math.min(leftMax[i],rightMax[i]);
            if (temp-height[i]<=0){
                continue;
            }
            res += temp - height[i];
        }

        return res;

    }
}

时间O(n)
空间O(2n)

动态规划单数组

leftMax rightMax都只依赖与左边和右边，且最终遍历时我们从左往右遍历，那么可以先优化掉leftMax。

class Solution {
    public int trap(int[] height) {
        //按列看接雨水，每一个柱子所在处能接的雨水 是它左边最大值和右边最大值 的较小者。

        //所以只需要求出每一个柱子对应的左侧最大值和右侧最大值即可。

        int leftMax = 0;
        int[] rightMax = new int[height.length];

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


        int res = 0;
        for(int i=1;i<height.length-1;i++){
            leftMax = Math.max(leftMax,height[i-1]);
            int temp =  Math.min(leftMax,rightMax[i]);
            if (temp-height[i]<=0){
                continue;
            }
            res += temp - height[i];
        }

        return res;

    }
}

时间O(n)
空间O(n)

动态规划+双指针

height [ left - 1] 是可能成为 max_left 的变量， 同理，height [ right + 1 ] 是可能成为 right_max 的变量。

只要保证 height [ left - 1 ] < height [ right + 1 ] ，那么 max_left 就一定小于 max_right。

因为 max_left 是由 height [ left - 1] 更新过来的，而 height [ left - 1 ] 是小于 height [ right + 1] 的，而 height [ right + 1 ] 会更新 max_right，所以间接的得出 max_left 一定小于 max_right。

public int trap(int[] height) {
    int sum = 0;
    int max_left = 0;
    int max_right = 0;
    int left = 1;
    int right = height.length - 2; // 加右指针进去
    for (int i = 1; i < height.length - 1; i++) {
        //从左到右更
        if (height[left - 1] < height[right + 1]) {
            max_left = Math.max(max_left, height[left - 1]);
            int min = max_left;
            if (min > height[left]) {
                sum = sum + (min - height[left]);
            }
            left++;
        //从右到左更
        } else {
            max_right = Math.max(max_right, height[right + 1]);
            int min = max_right;
            if (min > height[right]) {
                sum = sum + (min - height[right]);
            }
            right--;
        }
    }
    return sum;
}

时间O(n)
空间O(1)

按行接雨水

例如[6,3,1,0,1,3,6]
对于第一个3来说，按行接到的雨水=高*宽=(6-3)*3
对于第一个1来说，按行接到的雨水=(3-1)*3

单调栈

首先确定，按行接雨水，依赖的是每个元素左右两边第一个比它大的元素。
右边第一个更大元素好理解，我们之前的单调栈就可以实现：每次进栈，如果当前元素比栈顶元素大，说明当前元素就是要找的第一个更大元素。
左边第一个更大元素怎么理解呢？仔细思考，从栈底到栈顶，一定是递减的，所以当栈顶元素需要出队时，它的前一个元素，就是左边的第一个更大元素。

class Solution {
    public int trap(int[] height) {
        //按行接雨水。
        //对于每一个元素都要找到左右两边第一个比它大的数。

        //当前元素按行能接到的雨水 = 高（两边数的更小值-当前元素）*宽（右边第一个大数下标-左边第一个大数下标-1）

        Deque<Integer> s = new LinkedList<>();
        
        int res = 0;

        s.push(0);

        for(int i=1;i<height.length;i++){
            while(!s.isEmpty()&&height[i]>height[s.peek()]){
                //作为底的下标
                int lowerIndex = s.pop();
                
                if (s.isEmpty()){
                    //没有左边更大的元素了，不参与计算
                    break;
                }else{
                //取出左边更大元素的值，注意不是pop。
                    int leftIndex = s.peek();
                    int h = Math.min(height[leftIndex],height[i])-height[lowerIndex];
                    res += h*(i-leftIndex-1);
                }
            }
            s.push(i);
        }

        return res;
    }
}

时间O(n)
空间O(n)

柱状图中最大的矩形

class Solution {
    public int largestRectangleArea(int[] heights) {
        if (heights.length==1){
            return heights[0];
        }
        int res = 0;
        //先从暴力解法的思路来解决，遍历每一个柱子的时候，怎么确定矩阵的面积呢？
        //首先长度肯定是无法确定的，因为每一个柱子的长都是1，那就固定高度。
        //固定了某个高度的柱子，如何找到最大的矩形呢？
        //一定是向两边扩散，同时两边的柱子一定要比这个柱子高，否则无法扩展矩阵。

        //实际就是找某个柱子两边最先出现的比它更小的元素，直接联想到单调栈。

        Deque<Integer> s = new LinkedList<>();
        s.push(0);


        for(int i=1;i<heights.length;i++){
            while(!s.isEmpty()&&heights[i]<heights[s.peek()]){

                //定义(leftIndex,rightIndex)左开右开区间内，是用middleIndex为高度的最大矩阵。
                int middleIndex = s.pop();

                int leftIndex = -1;
                //栈不为空，说明左边有一样或低的元素
                //如果一样，那就抛弃这个元素
                while(!s.isEmpty()&&heights[s.peek()]==heights[middleIndex]){
                    s.pop();
                }
                if (!s.isEmpty()){
                    leftIndex = s.peek();
                }
                res = Math.max(res,(i-leftIndex-1)*heights[middleIndex]);
            }
            s.push(i);
        }

        //栈中剩下的元素，说明这些都是右边没有更小值了，需要求他们和左边拼成的面积
        while(!s.isEmpty()){
            int middleIndex = s.pop();
            //注意 因为右边没有更小值了，所以右边界一定是数组的长度
            int rightIndex = heights.length;

            int leftIndex = -1;
            //栈不为空，说明左边有一样或低的元素
            //如果一样，那就抛弃这个元素
            while(!s.isEmpty()&&heights[s.peek()]==heights[middleIndex]){
                s.pop();
            }
            if (!s.isEmpty()){
                leftIndex = s.peek();
            }
            res = Math.max(res,(rightIndex-leftIndex-1)*heights[middleIndex]);
        }
        return res;

    }
}

时间O(n)
空间O(n)