单调栈

单调栈

739. 每日温度

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

思路：这题一开始思路就是两个for循环暴力解开，但时间超出了限制，那么使用单调栈。单调栈就是用于找出左边或右边第一个大或小的数值，以空间换时间，可以压缩到O(n)的时间复杂度。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
     public int[] dailyTemperatures(int[] temperatures) {

        int lens=temperatures.length;
        int []res=new int[lens];
        Deque<Integer> stack=new LinkedList<>();
        stack.push(0);
        for(int i=1;i<lens;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;
    }
}

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，答案是使用hashmap，因为nums1和nums2都没有重复元素，因此可以建立hashmap，使用nums1[i]为key，i为value，建立起映射关系。这样就可以在两个数组上使用单调栈了。

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
class Solution {
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        Stack<Integer> temp = new Stack<>();
        int[] res = new int[nums1.length];
        //初始化是不存在下一个更大的元素
        Arrays.fill(res,-1);
        //由于没有重复元素，因此可以用hashmap来根据nums1[i]对i进行快速查找
        HashMap<Integer, Integer> hashMap = new HashMap<>();
        for (int i = 0 ; i< nums1.length ; i++){
            hashMap.put(nums1[i],i);
        }
        temp.add(0);
        //这里遍历的是nums2的数组，因为for里面一定是比较数组，存放的是比较数组的单调栈
        for (int i = 1; i < nums2.length; i++) {
            //这里表明了单调栈的逻辑：是一个从头到底递增的栈
            if (nums2[i] <= nums2[temp.peek()]) {
                temp.add(i);
            } else {
                while (!temp.isEmpty() && nums2[temp.peek()] < nums2[i]) {
                    //这里是关键的一步，打通nums1和nums2
                    if (hashMap.containsKey(nums2[temp.peek()])){
                        Integer index = hashMap.get(nums2[temp.peek()]);
                        res[index] = nums2[i];
                    }
                    //不要忘记弹出
                    temp.pop();
                }
                //当循环不满足，也就是递增的单调栈重新被满足了，就add进去
                temp.add(i);
            }
        }
        return res;
    }
}

503. 下一个更大元素 II

给定一个循环数组 nums （ nums[nums.length - 1] 的下一个元素是 nums[0] ），返回 nums 中每个元素的 下一个更大元素 。

数字 x 的 下一个更大的元素 是按数组遍历顺序，这个数字之后的第一个比它更大的数，这意味着你应该循环地搜索它的下一个更大的数。如果不存在，则输出 -1 。

思路：这题就是典型的单调栈，唯一的难点是如何实现循环搜索。其实也很简单，只需要在第一个for循环后，如果还有剩余的stack，就进入第二个for循环，该循环的目的也是找出右边的下一个最大元素。

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
class Solution {
    public int[] nextGreaterElements(int[] nums) {
        Stack<Integer> stack = new Stack<>();
        int[] res = new int[nums.length];
        Arrays.fill(res, -1);
        stack.add(0);
        for(int i = 1; i < nums.length; i++){
            if(nums[i] <= nums[stack.peek()]){
                stack.add(i);
            }else{
                while(!stack.isEmpty() && nums[i] > nums[stack.peek()]){
                    res[stack.peek()] = nums[i];
                    stack.pop();
                }
                stack.add(i);
            }
        }
        if(!stack.isEmpty()){
            for(int i = 0; i < nums.length; i++){
                while(!stack.isEmpty() && nums[i] > nums[stack.peek()]){
                    res[stack.peek()] = nums[i];
                    stack.pop();
                }
            }
        
        }
        return res;
        

    }
}

42. 接雨水

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

image-20240112132753718

思路：这题要学会化整为零，关键是找到每一个元素的高度能接多少雨水，而不是跳着接。直接的想法是双指针，该元素能接多少水，是由其左右两边第一个高过它的元素决定的，具体取决于哪个，就看哪个小了，可以用两个数组记录。第二种思路是单调栈，这种方法比较复杂，但思路也差不多，用一个递增的单调栈和一个判断当前元素是否大于栈顶元素的循环，来模拟左右两边第一个高过当前元素的元素。

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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
//双指针
class Solution {
    public int trap(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;
    }
}


//单调栈
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{
                //这种情况就是当前元素大于栈顶元素，要执行操作了
                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. 柱状图中最大的矩形

给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。

求在该柱状图中，能够勾勒出来的矩形的最大面积。

image-20240113103716653

思路：这题和接雨水非常像，唯一的区别在于接雨水是找左右两边离元素最近的第一个大于该元素的值，而该题是找左右两边离元素最远的小值。双指针解法比较通俗易懂，主要是注意while来不断寻找第一个小值，用result来保存最大的矩形值。

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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
//双指针
class Solution {
    public int largestRectangleArea(int[] heights) {
        int length = heights.length;
        int[] minLeftIndex = new int [length];
        int[] minRightIndex = new int [length];
        // 记录左边第一个小于该柱子的下标
        minLeftIndex[0] = -1 ;
        for (int i = 1; i < length; i++) {
            int t = i - 1;
            // 这里不是用if，而是不断向右寻找的过程
            while (t >= 0 && heights[t] >= heights[i]) t = minLeftIndex[t];
            minLeftIndex[i] = t;
        }
        // 记录每个柱子右边第一个小于该柱子的下标
        minRightIndex[length - 1] = length;
        for (int i = length - 2; i >= 0; i--) {
            int t = i + 1;
            while(t < length && heights[t] >= heights[i]) t = minRightIndex[t];
            minRightIndex[i] = t;
        }
        // 求和
        int result = 0;
        for (int i = 0; i < length; i++) {
            int sum = heights[i] * (minRightIndex[i] - minLeftIndex[i] - 1);
            result = Math.max(sum, result);
        }
        return result;
    }
}

//单调栈
class Solution {
    int largestRectangleArea(int[] heights) {
        Stack<Integer> st = new Stack<Integer>();
        
        // 数组扩容，在头和尾各加入一个元素，以便求得[0]和[length-1]的矩阵面积
        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++) {
            // 从顶到底是递减的，储存的是xia
            // 注意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;
    }
}
算法
#算法 #刷题
单调栈
https://wengerblogs.me/2025/05/13/单调栈/
Author
Wenger
Posted on
May 13, 2025
Licensed under