Posted Updated Leetcode8 minutes read (About 1131 words)0 visits

单调栈问题总结

Monotonic Stack问题总结

单调栈问题的思路就是栈中的元素都是单调增或者单调减的，当我们想要新加入元素到栈的时候，我们回去查看是否符合单调标准，不符合的弹出。
https://blog.csdn.net/qq_17550379/article/details/86519771

  1. Next Greater Element I：这道题是单调栈的代表问题与基础问题，是解决后面复杂问题的工具，也就是让我们找某个元素右侧最近的大于自身的元素，由于在遇到比自身大的元素之前可能中间会与其他元素，而这些其他元素的信息我们也是需要的，所以自然而然可以联想到栈的性质。
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
/*
496. Next Greater Element I
Easy

961

1543

Favorite

Share
You are given two arrays (without duplicates) nums1 and nums2 where nums1’s elements are subset of nums2. Find all the next greater numbers for nums1's elements in the corresponding places of nums2.

The Next Greater Number of a number x in nums1 is the first greater number to its right in nums2. If it does not exist, output -1 for this number.

Example 1:
Input: nums1 = [4,1,2], nums2 = [1,3,4,2].
Output: [-1,3,-1]
Explanation:
    For number 4 in the first array, you cannot find the next greater number for it in the second array, so output -1.
    For number 1 in the first array, the next greater number for it in the second array is 3.
    For number 2 in the first array, there is no next greater number for it in the second array, so output -1.
Example 2:
Input: nums1 = [2,4], nums2 = [1,2,3,4].
Output: [3,-1]
Explanation:
    For number 2 in the first array, the next greater number for it in the second array is 3.
    For number 4 in the first array, there is no next greater number for it in the second array, so output -1.
*/

class Solution {
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        Stack<Integer> stack = new Stack<>();
        Map<Integer, Integer> map = new HashMap<>();
        for(int num:nums2){
            while(!stack.isEmpty() && stack.peek()<num){
                map.put(stack.peek(), num);
                stack.pop();
            }
            stack.push(num);
        }
        
        int[] ans = new int[nums1.length];
        for(int i =0;i<=ans.length-1;i++){
            if(map.containsKey(nums1[i])){
                ans[i] = map.get(nums1[i]);
            }
            else {
                ans[i] = -1;
            }
        }
        
        return ans;
    }
}
  1. Next Greater Element II：这道题与前一道思路基本一致，有两点不同：保存的是index因为会有duplicates；array是一个环，所以遍历两遍。
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
/*
503. Next Greater Element II
Medium

860

49

Favorite

Share
Given a circular array (the next element of the last element is the first element of the array), print the Next Greater Number for every element. The Next Greater Number of a number x is the first greater number to its traversing-order next in the array, which means you could search circularly to find its next greater number. If it doesn't exist, output -1 for this number.

Example 1:
Input: [1,2,1]
Output: [2,-1,2]
Explanation: The first 1's next greater number is 2; 
The number 2 can't find next greater number; 
The second 1's next greater number needs to search circularly, which is also 2.
Note: The length of given array won't exceed 10000.*/

class Solution {
    public int[] nextGreaterElements(int[] nums) {
        Stack<Integer> stack = new Stack<>();
        int[] ans = new int[nums.length];
        Arrays.fill(ans, -1);
        for(int i=0;i<=nums.length-1;i++){
            while(!stack.isEmpty() && nums[stack.peek()]<nums[i]){
                ans[stack.pop()] = nums[i];
            }
            stack.push(i);
        }
        
        for(int i=0;i<=nums.length-1;i++){
            while(!stack.isEmpty() && nums[stack.peek()]<nums[i]){
                ans[stack.pop()] = nums[i];
            }
            stack.push(i);
        }
        
        return ans;
    }
}

有了上面两道题的铺垫，我们找到了单调栈解法这一工具，下面的题虽然看起来很复杂，但如果我们运用单调栈会将它们变得很简单。

  1. Trapping Rain Water：42与84属于镜像问题，一个是找某个index的最近的两边比他大的，一个是找某个index的最近的两边比他小的。
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. Trapping Rain Water
Hard

4727

83

Favorite

Share
Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining.


The above elevation map is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped. Thanks Marcos for contributing this image!

Example:

Input: [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6
*/

class Solution {
    public int trap(int[] height) {
        Stack<Integer> stack = new Stack<>();
        stack.push(-1);
        int ans = 0;
        for(int i =0;i<=height.length-1;i++){
            while(stack.peek()!=-1 && height[i]>height[stack.peek()]){
                int index = stack.pop();
                if(stack.peek()!=-1){
                    int minHeight = Math.min(height[stack.peek()], height[i]);
                    int waterHeight = minHeight - height[index];
                    ans = ans + waterHeight*(i-1-(stack.peek()+1)+1);
                }
            }
            stack.push(i);
        }
        return ans;
    }
}

84.Largest Rectangle in Histogram：我们在栈中储存高度单调递增的方块的索引，当我们遇到比栈顶小的方块，说明我们找到了右边界(就是遇到的这个比栈顶小的方块)，左边界(栈先pop出本方块，此时的peek是左边界)，所以我们就可以求得以这个方块高度为高的面积大小。
由于我们要查看栈顶来看我们的左侧边界，所以我们需要开率边界条件，也就是现在栈里面加一个-1。

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
/*
84. Largest Rectangle in Histogram
Hard

2424

63

Favorite

Share
Given n non-negative integers representing the histogram's bar height where the width of each bar is 1, find the area of largest rectangle in the histogram.

 


Above is a histogram where width of each bar is 1, given height = [2,1,5,6,2,3].

 


The largest rectangle is shown in the shaded area, which has area = 10 unit.
*/
class Solution {
    public int largestRectangleArea(int[] heights) {
        int ans = 0;
        Stack<Integer> stack = new Stack<>();
        stack.push(-1);
        for(int i = 0;i<=heights.length-1;i++){
            while(stack.peek()!=-1 && heights[i]<heights[stack.peek()]){
                int index = stack.pop();
                ans = Math.max(ans , heights[index]*(i-1-(stack.peek()+1)+1));
            }
            stack.push(i);
        }
        
        while(stack.peek()!=-1){
            int index = stack.pop();
            ans = Math.max(ans, heights[index]*(heights.length-1-(stack.peek()+1)+1));
        }
        
        return ans;
    }
}
  1. Minimum Cost Tree From Leaf Values：拿到这道题很容易想到变成dp去做，但那样时间空间复杂度都很高，我们可以使用greedy，这篇文章里面讲的很好。
    https://leetcode.com/problems/minimum-cost-tree-from-leaf-values/discuss/339959/One-Pass-O(N)-Time-and-Space
    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
    /*
    1130. Minimum Cost Tree From Leaf Values
    Medium

    286

    29

    Favorite

    Share
    Given an array arr of positive integers, consider all binary trees such that:

    Each node has either 0 or 2 children;
    The values of arr correspond to the values of each leaf in an in-order traversal of the tree.  (Recall that a node is a leaf if and only if it has 0 children.)
    The value of each non-leaf node is equal to the product of the largest leaf value in its left and right subtree respectively.
    Among all possible binary trees considered, return the smallest possible sum of the values of each non-leaf node.  It is guaranteed this sum fits into a 32-bit integer.

     

    Example 1:

    Input: arr = [6,2,4]
    Output: 32
    Explanation:
    There are two possible trees.  The first has non-leaf node sum 36, and the second has non-leaf node sum 32.

        24            24
       /  \          /  \
      12   4        6    8
     /  \               / \
    6    2             2   4
     

    Constraints:

    2 <= arr.length <= 40
    1 <= arr[i] <= 15
    It is guaranteed that the answer fits into a 32-bit signed integer (ie. it is less than 2^31).
    */
    class Solution {
        public int mctFromLeafValues(int[] arr) {
            Stack<Integer> stack = new Stack<>();
            stack.push(Integer.MAX_VALUE);
            int ans = 0;
            for(int number:arr){
                while(stack.peek()!=Integer.MAX_VALUE && number>=stack.peek()){
                    int num = stack.pop();
                    ans = ans + num * Math.min(number, stack.peek());
                }
                stack.push(number);
            }
            while(stack.size()>2){
                ans = ans + stack.pop()*stack.peek();
            }
            
            return ans;
            
            
        }
    }

由以上这三道题可以看出来，当我们需要同时求左侧和右侧的第一个最大(最小)值的时候，我们需要先在栈里面加入一个边界元素(也就是左侧没有更大(更小)的时候该怎么办)。还有这种问题不要忘记考虑最后剩在stack的元素。

  1. Sliding Window Maximum: 这道题本质上也是单调栈/队列，总共有三个操作(1. Deque的头元素在k的范围内，否则poll 2. Deque的尾元素如果小于遇到的新元素，poll 3. 在Deque尾部加入新元素)。经过这三个操作我们可以确保Deque中的元素都在sliding window的范围内且是单调的，所以这个时候我们取头元素即是该sliding window的最大值。
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
/*
239. Sliding Window Maximum
Hard

2278

134

Favorite

Share
Given an array nums, there is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves right by one position. Return the max sliding window.

Example:

Input: nums = [1,3,-1,-3,5,3,6,7], and k = 3
Output: [3,3,5,5,6,7] 
Explanation: 

Window position                Max
---------------               -----
[1  3  -1] -3  5  3  6  7       3
 1 [3  -1  -3] 5  3  6  7       3
 1  3 [-1  -3  5] 3  6  7       5
 1  3  -1 [-3  5  3] 6  7       5
 1  3  -1  -3 [5  3  6] 7       6
 1  3  -1  -3  5 [3  6  7]      7
Note:
You may assume k is always valid, 1 ≤ k ≤ input array's size for non-empty array.

Follow up:
Could you solve it in linear time?
*/
class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        if(nums==null || nums.length==0){
            return new int[0];
        }
        Deque<Integer> dq = new ArrayDeque<>();
        int[] ans = new int[nums.length-k+1];
        for(int i = 0;i<=nums.length-1;i++){
            while(dq.peekFirst()!=null && dq.peekFirst()<i-k+1){
                dq.pollFirst();
            }
            
            while(dq.peekLast()!=null && nums[dq.peekLast()]<nums[i]){
                dq.pollLast();
            }
            
            dq.offer(i);
            
            if(i>=k-1){
                ans[i-k+1] = nums[dq.peekFirst()];
            }
        }
        return ans;
        
    }
}
Follow

Catalogue

×