1.单调栈总结

1.1 经验总结

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

2.每日温度（力扣739）

//1.暴力
    public int[] dailyTemperatures(int[] temperatures) {
        if(temperatures == null || temperatures.length == 0) return null;
        int len = temperatures.length;

        int[] res = new int[len];
        for(int i = 0;i < len;i ++){
            for(int j = i;j < len;j ++){
                if(temperatures[j] > temperatures[i]){
                    res[i] = j - i;
                    break;
                }
            }
        }
        return res;
    }

//2.单调栈
    public int[] dailyTemperatures2(int[] temperatures) {
        if(temperatures == null || temperatures.length == 0) return null;
        int len = temperatures.length;

        Deque<Integer> stack = new LinkedList<>();
        int[] res = new int[len];
        for(int i = 0;i < len;i ++){
            //当栈不为空且当前数字大于之前数字，考虑更新数组
            while(!stack.isEmpty() && temperatures[i] > temperatures[stack.peek()]){
                int index = stack.pop();
                res[index] = i - index;
            }
            //如果栈为空或者是当前数字小于等于之前数字，将对应下标压入栈
            stack.push(i);
        }
        return res;
    }

3.下一个更大元素 I（力扣496）

//1.hashmap+双层for循环
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        int len1 = nums1.length,len2 = nums2.length;
        Map<Integer,Integer> map = new HashMap<>();
        //（key,value）-> （nums2的值，对应的下标）
        for(int i = 0;i < len2;i ++){
            map.put(nums2[i],i);
        }

        int[] res = new int[len1];
        Arrays.fill(res,-1);
        for(int i = 0;i < len1;i ++){
            for(int j = map.get(nums1[i]);j < len2;j ++){
                if(nums2[j] > nums1[i]){
                    res[i] = nums2[j];
                    break;
                }
            }
        }
        return res;
    }

//2.单调栈+hashmap
    public int[] nextGreaterElement2(int[] nums1, int[] nums2) {
        int len1 = nums1.length,len2 = nums2.length;
        Map<Integer,Integer> map = new HashMap<>();
        for(int i = 0;i < len2;i ++){
            map.put(nums2[i],i);
        }

        Deque<Integer> stack = new LinkedList<>();
        int[] res1 = new int[len2];
        Arrays.fill(res1,-1);
        for(int i = 0;i < len2;i ++){
            while(!stack.isEmpty() && nums2[i] > nums2[stack.peek()]){
                res1[stack.pop()] = nums2[i];
            }
            stack.push(i);
        }

        int[] res2 = new int[len1];
        for(int i = 0;i < len1;i ++){
            res2[i] = res1[map.get(nums1[i])];
        }

        return res2;
    }

//3.降低时间复杂度
    public int[] nextGreaterElement3(int[] nums1, int[] nums2) {
        int len1 = nums1.length,len2 = nums2.length;

        Deque<Integer> stack = new LinkedList<>();
        Map<Integer,Integer> map = new HashMap<>();
        for(int i = 0 ;i < len2;i ++){
            while(!stack.isEmpty() && nums2[i] > stack.peek()){
                map.put(stack.pop(),nums2[i]);
            }
            stack.push(nums2[i]);
        }

        int[] res = new int[len1];
        for(int i = 0;i < len1;i ++){
            res[i] = map.getOrDefault(nums1[i],-1);
        }
        return res;
    }

4.下一个更大元素 II（力扣503）

//1.单调栈
    public int[] nextGreaterElements(int[] nums) {
        if(nums == null || nums.length == 0) return null;
        int len = nums.length;

        int[] res = new int[len];
        Arrays.fill(res,-1);
        Deque<Integer> stack = new LinkedList<>();
        for(int i = 0;i < len * 2 - 1;i ++){
            while(!stack.isEmpty() && nums[i % len] > nums[stack.peek()]){
                res[stack.pop()] = nums[i % len];
            }
            stack.push(i % len);
        }
        return res;
    }

5.接雨水（力扣42）

//1.双指针（按照每一列来计算）
    public int trap(int[] height) {
        if(height == null || height.length == 0) return 0;
        int len = height.length;

        int sum = 0;
        for(int i = 0;i < len;i ++){
            //第一天和最后一天没法接雨水
            if(i == 0 || i == len - 1) continue;
            //分别代表当前柱子的左边和右边的最高柱子的高度
            int lHeight = height[i],rHeight = height[i];
            int left = i,right = i;
            while(left >= 0){
                if(height[left] > lHeight){
                    lHeight = height[left];
                }
                left --;
            }
            while(right < len){
                if(height[right] > rHeight){
                    rHeight = height[right];
                }
                right ++;
            }
            if(Math.min(lHeight,rHeight) > height[i]){
                sum += Math.min(lHeight,rHeight) - height[i];
            }
        }

        return sum;
    }

//2.动态规划避免重复操作
    public int trap2(int[] height) {
        int length = height.length;
        if (length <= 2) return 0;
        int[] maxLeft = new int[length];
        int[] maxRight = new int[length];

        // 记录每个柱子左边柱子最大高度
        maxLeft[0] = height[0];
        for (int i = 1; i< length; i++) maxLeft[i] = Math.max(height[i], maxLeft[i-1]);

        // 记录每个柱子右边柱子最大高度
        maxRight[length - 1] = height[length - 1];
        for(int i = length - 2; i >= 0; i--) maxRight[i] = Math.max(height[i], maxRight[i+1]);

        // 求和
        int sum = 0;
        for (int i = 0; i < length; i++) {
            int count = Math.min(maxLeft[i], maxRight[i]) - height[i];
            if (count > 0) sum += count;
        }
        return sum;
    }

//3.单调栈（维护一个从栈头到栈尾为从小到大的单调栈）
    public int trap3(int[] height) {
        if(height == null || height.length < 3) return 0;
        int len = height.length;
        Deque<Integer> stack = new LinkedList<>();

        int sum = 0;
        stack.push(0);
        for(int i = 1;i < len;i ++){
            //如果小于栈顶元素，直接入栈
            if(height[i] < height[stack.peek()]){
                stack.push(i);
                //如果等于栈顶元素，则替换栈顶元素
            }else if(height[i] == height[stack.peek()]){
                stack.pop();
                stack.push(i);
            }else{
                //如果大于栈顶元素，则统计以栈顶元素为底的每一个符合要求的容器的所有容量
                while(!stack.isEmpty() && height[i] > height[stack.peek()]){
                    //每次只弹出一个元素，依次计算以mid为底的所有容器的容量和
                    int mid = stack.pop();
                    if(!stack.isEmpty()){
                        int left = stack.peek();
                        int h = Math.min(height[i],height[left]) - height[mid];
                        sum += (h * (i - left - 1));
                    }
                }
                //不要忘记将当前位置压入栈中
                stack.push(i);
            }
        }
        return sum;
    }

6.柱状图中最大的矩形（力扣84）

//1.单调栈（维护一个递增栈）
    public int largestRectangleArea(int[] heights) {
        if(heights == null || heights.length == 0) return 0;
        int len = heights.length;
        //为了避免数组中为递增和{3,2}这种情况，扩充原数组，在前后补0
        int[] newheights = new int[len + 2];
        for(int i = 0;i < len;i ++){
            newheights[i + 1] = heights[i];
        }
        heights = newheights;

        int max = 0;
        Deque<Integer> stack = new LinkedList<>();
        stack.push(0);
        for(int i = 1;i < len + 2 ;i ++){
            if(heights[i] > heights[stack.peek()]){
                stack.push(i);
            }else if(heights[i] == heights[stack.peek()]){
                stack.pop();
                stack.push(i);
            }else{
                while(!stack.isEmpty() && heights[i] < heights[stack.peek()]){
                    int mid = stack.pop();
                    if(!stack.isEmpty()){
                        int left = stack.peek();
                        int h = heights[mid];
                        max = Math.max(max,h * (i - left - 1));
                    }
                }
                stack.push(i);
            }
        }
        return max;
    }