单调栈！！！

739. 每日温度

题目

给定一个整数数组 temperatures ，表示每天的温度，返回一个数组 answer ，其中 answer[i] 是指对于第 i 天，下一个更高温度出现在几天后。如果气温在这之后都不会升高，请在该位置用 0 来代替。
示例：

思路

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

本题其实就是找找到一个元素右边第一个比自己大的元素。
单调栈的本质是空间换时间，因为在遍历的过程中需要用一个栈来记录右边第一个比当前元素高的元素，优点是只需要遍历一次。
在使用单调栈的时候首先要明确如下几点：
（1）单调栈里存放的元素是什么？
单调栈里只需要存放元素的下标i就可以了，如果需要使用对应的元素，直接T[i]就可以获取。
（2）单调栈里元素是递增呢？ 还是递减呢？
注意一下顺序为 从栈头到栈底的顺序，这里要使用递增循序（再强调一下是指从栈头到栈底的顺序），因为只有递增的时候，加入一个元素i，才知道栈顶元素在数组中右面第一个比栈顶元素大的元素是i。
使用单调栈主要有三个判断条件。
（1）当前遍历的元素T[i]小于栈顶元素T[st.top()]的情况—> T[i]加入栈
（2）当前遍历的元素T[i]等于栈顶元素T[st.top()]的情况—> T[i]加入栈
（3）当前遍历的元素T[i]大于栈顶元素T[st.top()]的情况—> 弹出T[st.top()]，加入T[i]

代码

class Solution {
    public int[] dailyTemperatures(int[] temperatures) {
        int len = temperatures.length;
        int[] res = new int[len];

        //stack的元素是数组的下标
        Deque<Integer> stack = new LinkedList<>();
        stack.push(0);
        for(int i = 1; i < len; i++){
            if(temperatures[i] <= temperatures[stack.peek()]){
                stack.push(i);
            }else{
                while(!stack.isEmpty() && temperatures[i] > temperatures[stack.peek()]){
                    res[stack.peek()] = i - stack.peek();
                    stack.pop();
                }
                stack.push(i);
            }    
        }
        return res;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

496. 下一个更大元素 I

题目

nums1 中数字 x 的 下一个更大元素 是指 x 在 nums2 中对应位置 右侧 的 第一个 比 x 大的元素。给你两个没有重复元素 的数组 nums1 和 nums2 ，下标从 0 开始计数，其中nums1 是 nums2 的子集。
对于每个 0 <= i < nums1.length ，找出满足 nums1[i] == nums2[j] 的下标 j ，并且在 nums2 确定 nums2[j] 的 下一个更大元素 。如果不存在下一个更大元素，那么本次查询的答案是 -1 。
返回一个长度为 nums1.length 的数组 ans 作为答案，满足 ans[i] 是如上所述的 下一个更大元素 。
示例：

思路

要求nums1的每个元素在nums2中下一个比当前元素大的元素，那么就要定义一个和nums1一样大小的数组result来存放结果。
如果不存在对应位置就输出 -1 ，所以result数组如果某位置没有被赋值，那么就应该是是-1，所以就初始化为-1。
在遍历nums2的过程中，我们要判断nums2[i]是否在nums1中出现过，因为最后是要根据nums1元素的下标来更新result数组。
(1) Map
!!! 注意题目中说是两个没有重复元素 的数组 nums1 和 nums2。
没有重复元素，我们就可以用map来做映射了。根据数值快速找到下标，还可以判断nums2[i]是否在nums1中出现过。
(2)单调栈
栈头到栈底的顺序，要从小到大，也就是保持栈里的元素为递增顺序。只要保持递增，才能找到右边第一个比自己大的元素。
三种情况：
情况一：当前遍历的元素T[i]小于栈顶元素T[st.top()]的情况
此时满足递增栈（栈头到栈底的顺序），所以直接入栈。
情况二：当前遍历的元素T[i]等于栈顶元素T[st.top()]的情况
如果相等的话，依然直接入栈，因为我们要求的是右边第一个比自己大的元素，而不是大于等于！
情况三：当前遍历的元素T[i]大于栈顶元素T[st.top()]的情况
此时如果入栈就不满足递增栈了，这也是找到右边第一个比自己大的元素的时候。
判断栈顶元素是否在nums1里出现过，（注意栈里的元素是nums2的元素），如果出现过，开始记录结果。

代码

class Solution {
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        int len1 = nums1.length;
        int len2 = nums2.length;
        int[] res = new int[len1];
        Arrays.fill(res,-1);
        HashMap<Integer,Integer> map = new HashMap<>();
        for(int i = 0; i < len1; i++){
            map.put(nums1[i],i);
        }
        //数组下标
        Deque<Integer> stack = new LinkedList<>();
        stack.push(0);
        for(int i = 1; i < len2; i++){
            if(nums2[i] <= nums2[stack.peek()]){
                stack.push(i);
            }else{
                while(!stack.isEmpty() && nums2[i] > nums2[stack.peek()]){
                    if(map.containsKey(nums2[stack.peek()])){
                        int index = map.get(nums2[stack.peek()]);
                        res[index] = nums2[i];
                    }
                    stack.pop();
                }
                stack.push(i);
            }
        }
        return res;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

503. 下一个更大元素 II

题目

给定一个循环数组 nums （ nums[nums.length - 1] 的下一个元素是 nums[0] ），返回 nums 中每个元素的 下一个更大元素 。
数字 x 的 下一个更大的元素 是按数组遍历顺序，这个数字之后的第一个比它更大的数，这意味着你应该循环地搜索它的下一个更大的数。如果不存在，则输出 -1 。
示例：

思路：在遍历的过程中模拟走了两遍nums

代码

class Solution {
    public int[] nextGreaterElements(int[] nums) {
        int len = nums.length;
        int[] res = new int[len];
        Arrays.fill(res,-1);
        Deque<Integer> stack = new LinkedList<>();
        //遍历两次  i= i % len
        for(int i = 0; i < len * 2; i++){
            while(!stack.isEmpty() && nums[i % len] > nums[stack.peek()]){
                res[stack.peek()] = nums[i % len];
                stack.pop();
            }
            stack.push(i % len);
        }
        return res;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

42. 接雨水

题目

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
示例：

思路

动态规划

列4 左侧最高的柱子是列3，高度为2（以下用lHeight表示）。
列4 右侧最高的柱子是列7，高度为3（以下用rHeight表示）。
列4 柱子的高度为1（以下用height表示）
那么列4的雨水高度为 列3和列7的高度最小值减列4高度，即： min(lHeight, rHeight) - height。
列4的雨水高度求出来了，宽度为1，相乘就是列4的雨水体积了。

只要记录左边柱子的最高高度 和 右边柱子的最高高度，就可以计算当前位置的雨水面积，这就是通过列来计算。
当前列雨水面积：min(左边柱子的最高高度，记录右边柱子的最高高度) - 当前柱子高度。

单调栈

1.首先单调栈是按照行方向来计算雨水

2.使用单调栈内元素的顺序
从栈头（元素从栈头弹出）到栈底的顺序应该是从小到大的顺序。
因为一旦发现添加的柱子高度大于栈头元素了，此时就出现凹槽了，栈头元素就是凹槽底部的柱子，栈头第二个元素就是凹槽左边的柱子，而添加的元素就是凹槽右边的柱子。

3.遇到相同的元素，更新栈内下标，就是将栈里元素（旧下标）弹出，将新元素（新下标）加入栈中。
例如 5 5 1 3 这种情况。如果添加第二个5的时候就应该将第一个5的下标弹出，把第二个5添加到栈中。
因为我们要求宽度的时候 如果遇到相同高度的柱子，需要使用最右边的柱子来计算宽度。

4.栈里要保存什么数值
是用单调栈，其实是通过 长 * 宽 来计算雨水面积的。
长就是通过柱子的高度来计算，宽是通过柱子之间的下标来计算

栈里 存着下标，计算的时候用下标对应的柱子高度

5.处理逻辑
先将下标0的柱子加入到栈中，st.push(0);然后开始从下标1开始遍历所有的柱子，for (int i = 1; i < height.size(); i++)。
三种情况：
（1）如果当前遍历的元素（柱子）高度小于栈顶元素的高度，就把这个元素加入栈中，因为栈里本来就要保持从小到大的顺序（从栈头到栈底）。
（2）如果当前遍历的元素（柱子）高度等于栈顶元素的高度，要跟更新栈顶元素，因为遇到相相同高度的柱子，需要使用最右边的柱子来计算宽度。
（3）如果当前遍历的元素（柱子）高度大于栈顶元素的高度，此时就出现凹槽了：

取栈顶元素，将栈顶元素弹出，这个就是凹槽的底部，下标记为mid，对应的高度为height[mid].（就是图中的高度1)
此时的栈顶元素st.peek()，就是凹槽的左边位置，下标为st.peek()，对应的高度为height[st.peek()]（就是图中的高度2）。
当前遍历的元素i，就是凹槽右边的位置，下标为i，对应的高度为height[i]（就是图中的高度3)
雨水高度是 min(凹槽左边高度, 凹槽右边高度) - 凹槽底部高度，代码为：int h = min(height[st.peek()], height[i]) - height[mid];
雨水的宽度是 凹槽右边的下标 - 凹槽左边的下标 - 1（因为只求中间宽度），代码为：int w = i - st.peek() - 1 ;
当前凹槽雨水的体积就是：h * w

代码

class Solution {
    public int trap(int[] height) {
        int len = height.length;
        if(len <= 2)  return 0;
        int sum = 0;
        Deque<Integer> stack = new LinkedList<>();
        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()]){
                    int mid = stack.peek();
                    stack.pop();
                    if(!stack.isEmpty()){
                        int h = Math.min(height[i],height[stack.peek()])-height[mid];
                        int w = (i-stack.peek()) - 1;
                        if(h > 0)  sum += h * w;
                    }
                }
                stack.push(i);
            }

        }
        return sum;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

84. 柱状图中最大的矩形

题目

给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。求在该柱状图中，能够勾勒出来的矩形的最大面积。
示例：

思路

42.接雨水 是找每个柱子左右两边第一个大于该柱子高度的柱子，而本题是找每个柱子左右两边第一个小于该柱子的柱子。所以从栈头（元素从栈头弹出）到栈底的顺序应该是从大到小的顺序！
栈顶和栈顶的下一个元素以及要入栈的三个元素组成了我们要求最大面积的高度和宽度
剩下就是分析清楚如下三种情况：
情况一：当前遍历的元素heights[i]小于栈顶元素heights[st.top()]的情况
情况二：当前遍历的元素heights[i]等于栈顶元素heights[st.top()]的情况
情况三：当前遍历的元素heights[i]大于栈顶元素heights[st.top()]的情况

代码

class Solution {
    public int largestRectangleArea(int[] heights) {
        //从栈顶到栈底：从小到大，小于栈顶元素，弹出；大于等于，入栈
        int len = heights.length;
        int[] newHeights = new int[len+2];
        newHeights[0] = 0;
        newHeights[len+1] = 0;
        for(int i = 0; i < len; i++){
            newHeights[i+1] = heights[i];
        }
        heights = newHeights;
        
        int sum = 0;
        Deque<Integer> stack = new LinkedList<>();
        stack.push(0);
        for(int i = 1; i < heights.length; i++){
            while(!stack.isEmpty() && heights[i] < heights[stack.peek()]){
                int mid = stack.peek();
                stack.pop();
                int w = (i - stack.peek()) - 1;  
                int h = heights[mid];
                sum = Math.max(sum,w * h);  
            }
            stack.push(i);
        }
        return sum;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

85. 最大矩形

题目

给定一个仅包含 0 和 1 、大小为 rows x cols 的二维二进制矩阵，找出只包含 1 的最大矩形，并返回其面积。
示例：

思路

代码

class Solution {
    public int maximalRectangle(char[][] matrix) {
        int maxArea = 0;
        int m = matrix.length, n = matrix[0].length;
        int[] height = new int[n];
        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                if(matrix[i][j] == '1')
                    height[j] += 1;
                else
                    height[j] = 0;        
            }
            maxArea = Math.max(maxArea,largestRectangleArea(height));
        }
        return maxArea;


    }
    public int largestRectangleArea(int[] heights) {
        //从小到大 --- 小于栈顶元素就出栈
        int len = heights.length;
        int[] newHeight = new int[len+2];
        int sum = 0;
        newHeight[0] = 0;
        newHeight[len+1] = 0;
        for(int i = 0; i < len; i++){
            newHeight[i+1] = heights[i];
        }
        heights = newHeight;

        Deque<Integer> stack = new LinkedList<>();
        stack.push(0);
        for(int i = 1; i < heights.length; i++){
            while(heights[i] < heights[stack.peek()]){
                int mid = stack.peek();
                stack.pop();
                int h = heights[mid];
                int w = (i - stack.peek())-1;
                sum = Math.max(sum,h*w);
            }
            stack.push(i);
        }
        return sum;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45