单调栈题集

​ 单调栈是一种特殊的栈，因为栈中的元素大小是单调的而得名单调栈。经过预处理(预处理的时间复杂度为O(n))，可以在O(1)的时间复杂度求出数组中每个元素右边(左边)第一个大于(小于)该元素的值的下标。是一种非常常用且好用的数据结构

LeetCode84

​ 这道题我一开始的想的暴力做法是枚举两个自由度，第一个自由度表示该矩形的起始位置(start)，另一个自由度表示该矩形的结束位置(end)，在枚举的过程中维护一个最小高度(minH)并更新答案

1
2
3
4
5
6
7
8
9
10
int res = 0;

for(int i = 0; i < n; i ++){
   int minH = heights[i];
   res = Math.max(res,minH);
   for(int j = i + 1; j < n; j ++){
       minH = Math.min(minH,heights[j]);
       res = Math.max(res,(j - i + 1) * minH);
   }
}

​ 这似乎也是一种暴力思路，但是由于我一开始想的暴力做法是以上做法，导致我想利用双指针来进行优化，还是没想出来。

​ 但其实还有另一种暴力思路，枚举当前该高度能够形成的最大矩形，也要枚举两个自由度，一个就是数组中的每个高度height，另一个就是左右两边第一个比它小的高度的下标minL，minR，该矩形的面积就是height * (minL - minR)。在这种思路下，我一下子就想到了使用单调栈来优化。因为单调栈能够在O(1)的时间复杂度内得到左右两边第一个小于某个数的下标(在经过预处理的情况下)，因此总的时间复杂度为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
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
class Solution {
    public int largestRectangleArea(int[] heights) {
        int n = heights.length;
        int minL[] = new int[n];//minL[i]表示左边第一个小于heights[i]的下标
        int minR[] = new int[n];//minR[i]表示右边第一个小于heights[i]的下标
		//预处理
        Stack<Integer>stack = new Stack<>();
        for(int i = n - 1; i >= 0; i --){
            while(!stack.isEmpty() && heights[stack.peek()] >= heights[i]){
                stack.pop();
            }

            if(stack.isEmpty()){
                minR[i] = n;
            }else{
                minR[i] = stack.peek();
            }

            stack.push(i);
        }

        stack.clear();
        for(int i = 0; i < n; i ++){
            while(!stack.isEmpty() && heights[stack.peek()] >= heights[i]){
                stack.pop();
            }

            if(stack.isEmpty()){
                minL[i] = -1;
            }else{
                minL[i] = stack.peek();
            }

            stack.push(i);
        }

        int res = 0;
        //枚举每个高度下能够形成的最大矩形
        for(int i = 0; i < n; i ++){
            int s = heights[i] * (minR[i] - minL[i] - 1);
            res = Math.max(res,s);
        }

        return res;
    }
}

LeetCode962

​ 本题求解的问题是：大于某个数且距离最远的数的位置。暴力做法是枚举两个自由度，枚举每个数再枚举每个比它大的数,时间复杂度为O(n^2^).稍微优化的做法是在枚举比它大的数时可以倒着枚举，如果发现距离比当前答案还小就可以剪枝。

​ 一种更加优化的做法是利用单调栈，因为要求解距离最大值，可以预处理处以A[0]为起始点的递减序列，这个序列就是暴力做法中的一个自由度(意味着我们不必枚举每个数，而只要枚举这个序列中的数)。可以使用反证法证明这个自由度一定位于该递减序列中，如果答案是i-k，且k不在此递减序列中，那么意味着k前面没有比它更小的数，但这也意味着k位于该递减序列中(因为我们的递减序列是以下标为0开始的)。接下来，只要倒着枚举另一个自由度即可。(一旦比栈中数大，更新答案)。

实现代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public int maxWidthRamp(int[] nums) {
        int res = 0;
        int n = nums.length;
        Stack<Integer>min = new Stack<>();

        min.push(0);
        for(int i = 0; i < n; i ++){
            if(nums[i] < nums[min.peek()])min.push(i);
        }

        for(int i = n - 1; i >= 0; i --){
            while(!min.isEmpty() && nums[min.peek()] <= nums[i]){
                res = Math.max(res,i - min.peek());
                min.pop();
            }
        }

        return res;
    }
}

​