代码随想录-单调栈

单调栈

单调栈的使用场景：

通常是一维数组，要寻找任一个元素的右边或者左边第一个比自己大或者小的元素的位置。主要用于解决滑动窗口问题。

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

739.每日温度

/**
本题要寻找的是 ： 第一个比左边大的数字。
所以在栈中，递增（指栈头到栈底递增），即栈顶最小
这样出栈的时候，小的先出
使用单调栈主要有三个判断条件。
    当前遍历的元素T[i]小于栈顶元素T[st.top()]的情况
    当前遍历的元素T[i]等于栈顶元素T[st.top()]的情况
    当前遍历的元素T[i]大于栈顶元素T[st.top()]的情况

 */
class Solution {

    public int[] dailyTemperatures(int[] temperatures) {

        int lens=temperatures.length;
        // 返回的结果
        int []res = new int[lens];
        /**
        要找的：数组每个值，右边第一个比它大的值
        单调栈：最小的数组值下标在栈头，最大的数组值下标在栈尾
        如果当前遍历的元素 小于栈顶元素 ：它最小，进栈就行了
        如果当前遍历的元素 大于栈顶元素 ：栈顶元素要找的第一个最大值就是此元素
            所以就记录栈顶元素，然后弹出（一直弹出，直到栈顶比它大）
            如果栈弹空了，就说明：之前遍历的所有数都比它小
        那么当前遍历的元素大于栈顶元素时，怎么弹出栈顶并且记录？
            先记录，再弹出。
            记录：res[stack.peek()] = i-stack.peek();即对于当前栈顶元素（stack.peek()），它右边第i-stack.peek()值比他大
        
         */
        /**
        如果当前遍历的元素 大于栈顶元素，表示 栈顶元素的 右边的最大的元素就是 当前遍历的元素，
        	所以弹出 栈顶元素，并记录
        	如果栈不空的话，还要考虑新的栈顶与当前元素的大小关系
        否则的话，可以直接入栈。
        注意，单调栈里 加入的元素是 下标。
        */
        Deque<Integer> stack = new LinkedList<>();
        // 栈里存的是下标
        stack.push(0);
        // O(n)遍历原始数组
        for(int i = 1; i < lens ;i++){
            // temperatures[i]和栈顶比较，因为这里是递增栈，所以比栈顶 小或等于 就入栈
            if(temperatures[i] <= temperatures[stack.peek()]){
                stack.push(i);
            }else{
                // temperatures[i]比栈顶大，就要先弹出里面的再将temperatures[i]进栈
                // 注意这里的弹出方法
                while(!stack.isEmpty() && temperatures[i] > temperatures[stack.peek()]){
                    res[stack.peek()] = i-stack.peek();
                    stack.pop();
                }
                stack.push(i);
            }
        }

        return  res;
    }

}

496.下一个更大元素Ⅰ

单调栈，栈里存的是数组下标 ，和739.每日温度相同思路

/**
单调栈。
要返回的：一个数组，里面是A数组里的在数字在B数组里面右边的更大值的位置。
想法 ： 739是求单独一个数组，这里是求两个数组。先单独求B的下一个更大元素，再用A在B里找就行。
栈里要放的：注意 ：是下标  (但这里要求的是数组值，所以最后要处理一下)

 */
class Solution {
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        int len1 = nums1.length;
        int len2 = nums2.length;
        int[] resA = new int[len1];
        int[] resB = new int[len2];
        Deque<Integer> stack = new LinkedList<>();
        // 先单独求B的最大元素。
        stack.push(resB[0]);
        for(int i = 1;i < len2; i++){
            // nums2[i]和栈顶比较，因为这里是递增栈，所以比栈顶 小或等于 就入栈
            if(nums2[i] <= nums2[stack.peek()]){
                stack.push(i);
            }else{
                // 注意这里的弹出方法
                while(!stack.isEmpty() && nums2[i] > nums2[stack.peek()]){
                    resB[stack.peek()] = i-stack.peek();
                    stack.pop();
                }
                stack.push(i);
            }
        }
        // for(int i = 0;i < len2;i ++){
        //     System.out.println(resB[i]);
        // }
        //resB[i]代表的是，对于数组nums2中的第i个元素，第一个比它大的值在它右边第resB[i]个位置 
        //所以第一个比它大的值 ： nums2[i + resB[i]]
        for(int i = 0;i < len1; i ++){
            for(int j = 0;j < len2; j ++){
                if(nums1[i] == nums2[j]){
                    resA[i] = resB[j] == 0 ? -1 : nums2[j + resB[j]];
                }
            }
        }
        return resA;

    }
}

503.下一个更大元素Ⅱ

/**
单调栈来写 
给定一个循环数组，求循环数组中每个元素的下一个更大的值
注意 ： 这里是循环数组，所以除非nums[i] 是这个数组里的最大值 ，否则一定能找到它的下一个更大值
方法 ： 直接把原数组复制一份并连接在原数组后面，然后正常求
 */
class Solution {
    public int[] nextGreaterElements(int[] nums) {
        int len = nums.length;
        //返回数组
        int[] res = new int[len];
        //复制数组
        int[] numsCopy = new int[len * 2];
        int[] resCopy = new int[len * 2];
        for(int i = 0; i < len ;i ++){
            numsCopy[i] = nums[i];
            numsCopy[i + len] = nums[i];
        }
        //单调栈，里面存的是下标
        Deque<Integer> stack = new LinkedList<Integer>();
        stack.push(0);
        for(int i = 0 ;i < len * 2 ; i ++){
            //要求的是右边的最大数，因此比这个数小的数全都入栈，这样形成了栈顶最小的单调栈
            if(numsCopy[i] <= numsCopy[stack.peek()]){
                stack.push(i);
            }else{
                //现在是当前值比栈顶大了 ，那么就一直出栈并且记录，直到栈空或者当前值小于等于栈顶
                while(stack.peek() != null && numsCopy[i] > numsCopy[stack.peek()]){
                    resCopy[stack.peek()] = i - stack.peek();
                    stack.pop();
                }
                //出栈结束后，再把当前值入栈
                stack.push(i);
            }
        }
        // for(int i = 0; i < len * 2 ; i ++){
        //     System.out.println(resCopy[i]);
        // }

        //然后处理res[]
        for(int i = 0 ; i < len ; i ++){
            res[i] = resCopy[i] == 0 ? -1 : numsCopy[i + resCopy[i]];
        }
        return res;
    }
}

42.接雨水

想清楚怎么接

/**
单调栈 
具体思路 ： 
首先肯定是要找两个柱子中间有凹槽，这样才能存水。
那么已经有了一根柱子之后，从左往右看 ，要找的是第一个大于等于这个柱子高度的另一根柱子
如果当前遍历的元素（柱子）高度等于栈顶元素的高度：
    要跟更新栈顶元素，因为遇到相相同高度的柱子，需要使用最右边的柱子来计算宽度。
如果当前遍历的元素（柱子）高度大于栈顶元素的高度：
    此时就出现凹槽了，体积 = 高*宽
    高 = min(凹槽左边高度, 凹槽右边高度) - 凹槽底部高度
    宽 = 凹槽右边的下标 - 凹槽左边的下标 - 1（因为只求中间宽度）
 */
class Solution {
    public int trap(int[] height){
        int size = height.length;

        if (size <= 2) return 0;

        Stack<Integer> stack = new Stack<Integer>();
        stack.push(0);

        int sum = 0;
        for (int index = 1; index < size; index++){
            int stackTop = stack.peek();
            if (height[index] < height[stackTop]){
                stack.push(index);
            }else if (height[index] == height[stackTop]){
                // 因为相等的相邻墙，左边一个是不可能存放雨水的，所以pop左边的index, push当前的index
                stack.pop();
                stack.push(index);
            }else{
                //pop up all lower value
                int heightAtIdx = height[index];
                while (!stack.isEmpty() && (heightAtIdx > height[stackTop])){
                    int mid = stack.pop();

                    if (!stack.isEmpty()){
                        int left = stack.peek();

                        int h = Math.min(height[left], height[index]) - height[mid];
                        int w = index - left - 1;
                        int hold = h * w;
                        if (hold > 0) sum += hold;
                        stackTop = stack.peek();
                    }
                }
                stack.push(index);
            }
        }

        return sum;
    }
}

84.柱状图中最大矩形

和接雨水相反的操作

/**
最大面积受限于高和宽
因此这里用单调栈来做，但是栈顶是最大值 。
栈顶和栈顶的下一个元素以及要入栈的三个元素组成了我们要求最大面积的高度和宽度 
 */
class Solution {
    int largestRectangleArea(int[] heights) {
        Stack<Integer> st = new Stack<Integer>();
        
        // 数组扩容，在头和尾各加入一个元素
        int [] newHeights = new int[heights.length + 2];
        newHeights[0] = 0;
        newHeights[newHeights.length - 1] = 0;
        for (int index = 0; index < heights.length; index++){
            newHeights[index + 1] = heights[index];
        }

        heights = newHeights;
        
        st.push(0);
        int result = 0;
        // 第一个元素已经入栈，从下标1开始
        for (int i = 1; i < heights.length; i++) {
            // 注意heights[i] 是和heights[st.top()] 比较 ，st.top()是下标
            if (heights[i] > heights[st.peek()]) {
                st.push(i);
            } else if (heights[i] == heights[st.peek()]) {
                st.pop(); 
                st.push(i);
            } else {
                while (heights[i] < heights[st.peek()]) { // 注意是while
                    int mid = st.peek();
                    st.pop();
                    int left = st.peek();
                    int right = i;
                    int w = right - left - 1;
                    int h = heights[mid];
                    result = Math.max(result, w * h);
                }
                st.push(i);
            }
        }
        return result;
    }
}