【算法】单调栈

发表于2021-11-25更新于2021-12-22字数统计2.5k阅读时长19分阅读次数

单调栈结构

遍历整个数组，使用一个栈记录数组中的元素索引。

所有元素不重复的情况

  • 当寻找某个元素左右距离他最近的比他小的元素时，栈底元素的值小于栈顶元素的值。例如栈中：[2 -> 3 -> 4(栈顶)。新来一个元素1，其值小于4，则找到了当前栈顶4左右侧距离他最近的比他小的元素3和1。将4弹出，记录其左右侧的3和1，然后继续。
  • 当寻找某个元素左右距离他最近的比他大的元素时，栈底元素大于栈顶元素。例如栈中：[4 -> 3 -> 2(栈顶)。新来一个元素5，其值大于2，则找到了当前栈顶2左右侧距离他最近的比他大的元素3和5。

规律：

  • 整体是满足单调性的。当发现新来的元素破坏了栈中的单调性时，将栈顶元素弹出（其余元素不弹出，新来的元素也不在此时入栈，而是进行下一轮判断是否可以入栈），记录此时新的栈顶元素作为其左侧最近元素，记录新来的元素为其右侧最近元素。
  • 栈中保存的元素始终是按照升序或降序排列的，肯定满足单调性。这是因为中途破坏单调性的元素都被弹出并记录了，还在栈中的都是单调排序的。
  • 找某个元素左右比他小的，栈中是升序排列；找某个元素左右比他大的，栈中是降序排列。

有元素重复的情况

当有元素重复时，栈中不能单单只存储一个 Integer 类型变量，而应该存储一个 ArrayList，将相同值的元素存储到同一个 List 中。

算法整体顺序一致，区别在于弹栈时弹出的是一个 List，需要将这个 List 中的所有元素都遍历一次，加入到 res[][] 中；另外，在获取左侧的元素索引值时，需要获取到栈顶第二个 List 里的最后一个元素（这个元素是最靠近当前弹出栈的元素的，因为整体是单调的，越靠后的，越在 List 的后面）。

代码：

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
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
public class MonotonousStack {

   public static int[][] getNearLessNoRepeat(int[] nums) {
      if (nums == null || nums.length < 1) {
         return null;
      }

      Stack<Integer> stack = new Stack<>();
      int[][] res = new int[nums.length][2];

      for (int i = 0; i < nums.length; i++) {
         // 如果遇到栈顶元素大于当前元素，说明栈顶元素找到了其左侧小于它的第一个元素（栈顶下的第二个的元素）
         // 如果新来的元素仍是按照升序或降序排列，则都不会弹栈，因为仍然是符合单调性的，只有在破坏单调性时才弹栈记录
         while (!stack.isEmpty() && nums[stack.peek()] > nums[i]) {
            int popIndex = stack.pop();
            // 弹出的栈顶元素左侧的最小值就是新的栈顶元素（或不存在，对应栈空）
            int leftLessIndex = stack.isEmpty() ? -1 : stack.peek();
            // 存储这个栈顶元素的左侧小于它的第一个元素索引 leftLessIndex 和其右边小于它的第一个元素索引 i
            res[popIndex][0] = leftLessIndex;
            res[popIndex][1] = i;
         }
         // 跳出while循环时，i位置的元素已经能插入到栈中并满足栈中的单调性了，此时将i压入栈中
         stack.push(i);
      }

      // 遍历完数组后，栈中可能还存在一些元素，这些元素的最近元素还没保存到res里
      // 将栈中元素依次弹出，其左侧最近值就是下一个栈中元素，右侧最近值不存在，保存-1
      while (!stack.isEmpty()) {
         int popIndex = stack.pop();
         int leftLessIndex = stack.isEmpty() ? -1 : stack.peek();
         res[popIndex][0] = leftLessIndex;
         res[popIndex][1] = -1;
      }
      return res;
   }


   public static int[][] getNearLess(int[] nums) {
      if (nums == null || nums.length < 1) {
         return null;
      }

      Stack<List<Integer>> stack = new Stack<>();
      int[][] res = new int[nums.length][2];
      for (int i = 0; i < nums.length; i++) {
         while (!stack.isEmpty() && nums[stack.peek().get(0)] > nums[i]) {
            // 获取到list集合，里面可能存着多个相同值的元素
            List<Integer> popList = stack.pop();
            // 左边最小的元素为新的栈顶集合里的最后一个元素，因为最后一个元素是最靠近当前元素的（因为栈结构的单调性）
            int leftLessIndex = stack.isEmpty() ? -1 :stack.peek().get(stack.peek().size() - 1);
            // 遍历当前list里的元素（值相同），为其赋上左边最小元素索引（是相同的）以及右侧元素（i）
            for (Integer popIndex : popList) {
               res[popIndex][0] = leftLessIndex;
               res[popIndex][1] = i;
            }
         }
         // 将i加入到栈中，注意分两种情况：
         //   1. i的值和当前栈顶元素的值不相同，则新建一个list，将该list入栈
         //   2. i的值和当前栈顶元素的值相同，则将i加入到栈顶元素的list里的最后一个位置
         // 注意要带上 !stack.isEmpty() && ，必须要有元素才行
         if (!stack.isEmpty() && nums[stack.peek().get(0)] == nums[i]) {
            // 相同时，直接加入到栈顶的list中
            stack.peek().add(i);
         } else {
            // 不同时，新建一个list，入栈
            List<Integer> list = new ArrayList<>();
            list.add(i);
            stack.push(list);
         }
      }

      // 全部遍历完毕后，依次弹栈，记录栈中元素的左侧最小信息到res中
      while (!stack.isEmpty()) {
         List<Integer> popList = stack.pop();
         for (Integer popIndex : popList) {
            int leftLessIndex = stack.isEmpty() ? -1 : stack.peek().get(stack.peek().size() - 1);
            res[popIndex][0] = leftLessIndex;
            res[popIndex][1] = -1;
         }
      }

      return res;
   }

   // for test
   public static int[] getRandomArrayNoRepeat(int size) {
      int[] arr = new int[(int) (Math.random() * size) + 1];
      for (int i = 0; i < arr.length; i++) {
         arr[i] = i;
      }
      for (int i = 0; i < arr.length; i++) {
         int swapIndex = (int) (Math.random() * arr.length);
         int tmp = arr[swapIndex];
         arr[swapIndex] = arr[i];
         arr[i] = tmp;
      }
      return arr;
   }

   // for test
   public static int[] getRandomArray(int size, int max) {
      int[] arr = new int[(int) (Math.random() * size) + 1];
      for (int i = 0; i < arr.length; i++) {
         arr[i] = (int) (Math.random() * max) - (int) (Math.random() * max);
      }
      return arr;
   }

   // for test
   public static int[][] rightWay(int[] arr) {
      int[][] res = new int[arr.length][2];
      for (int i = 0; i < arr.length; i++) {
         int leftLessIndex = -1;
         int rightLessIndex = -1;
         int cur = i - 1;
         while (cur >= 0) {
            if (arr[cur] < arr[i]) {
               leftLessIndex = cur;
               break;
            }
            cur--;
         }
         cur = i + 1;
         while (cur < arr.length) {
            if (arr[cur] < arr[i]) {
               rightLessIndex = cur;
               break;
            }
            cur++;
         }
         res[i][0] = leftLessIndex;
         res[i][1] = rightLessIndex;
      }
      return res;
   }

   // for test
   public static boolean isEqual(int[][] res1, int[][] res2) {
      if (res1.length != res2.length) {
         return false;
      }
      for (int i = 0; i < res1.length; i++) {
         if (res1[i][0] != res2[i][0] || res1[i][1] != res2[i][1]) {
            return false;
         }
      }

      return true;
   }

   // for test
   public static void printArray(int[] arr) {
      for (int i = 0; i < arr.length; i++) {
         System.out.print(arr[i] + " ");
      }
      System.out.println();
   }

   public static void main(String[] args) {
      int size = 10;
      int max = 20;
      int testTimes = 2000000;
      for (int i = 0; i < testTimes; i++) {
         int[] arr1 = getRandomArrayNoRepeat(size);
         int[] arr2 = getRandomArray(size, max);
         if (!isEqual(getNearLessNoRepeat(arr1), rightWay(arr1))) {
            System.out.println("Oops!");
            printArray(arr1);
            break;
         }
         if (!isEqual(getNearLess(arr2), rightWay(arr2))) {
            System.out.println("Oops!");
            printArray(arr2);
            break;
         }
      }
   }
}

单调栈的相关题目

数组中累积和与最小值的乘积

定义指标A：正数数组中累积和与最小值的乘积。给定一个数组，请返回子数组中，指标A最大的值。

该问题可以使用单调栈结构进行求解。思路：

  • 遍历每一个元素，以该元素作为当前子区间内的最小值元素（其子区间内的元素都比当前元素大）；
  • 尽可能的扩大该子区间的范围，使得当前元素为最小值的子区间范围尽可能的大，这样其数组中的累加和就会尽可能的大；
  • 找到当前元素左右侧区间边界的方法为：使用单调栈找出当前元素左侧和右侧距离他最近的比他小的元素
  • 对数组中每个元素都进行该操作，直到找出最大的指标A
  • 可以在单调栈的建立过程中更新最大的指标A，无需创建索引后再单独计算

代码：

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
public class MonotonousStack {
    public static int solution(int[] nums) {
        if (nums == null || nums.length < 1) {
            return -1;
        }

        // 数组的前缀累加和
        int[] sums = new int[nums.length];
        // 初始化第一个元素
        sums[0] = nums[0];
        // 遍历每一个元素,计算前缀累加和
        for (int i = 1; i < nums.length; i++) {
            sums[i] = sums[i - 1] + nums[i];
        }

        Stack<Integer> stack = new Stack<>();
        // 记录答案
        int max = Integer.MIN_VALUE;
        for (int i = 0; i < nums.length; i++) {
            // 注意单调栈里保存的是索引值
            // 如果当前栈顶元素大于新来的元素,则找到了当前栈顶元素左右离他最近的元素,将其弹出
            // 注意是 while 循环，不断判断当前元素 nums[i] 与新的栈顶的大小，可能会一直弹出
            while (!stack.isEmpty() && nums[stack.peek()] >= nums[i]) {
                // 弹出栈顶元素，更新指标A的最大值
                // 注意这两个边界值的元素值都比当前元素小
                int j = stack.pop();
                // 1. 如果栈空，则不存在比他小的左边界，可以一直取到nums[0]，则当前子区间的累加和等于sums[i-1]（不能包含i值，因为其小于nums[j]）
                // 2. 如果栈不为空，则存在比他小的左边界且该边界值取不到，则当前子区间的累加和等于sums[i - 1] - sums[stack.peek()]
                max = Math.max(max, (stack.isEmpty() ? sums[i - 1] : (sums[i - 1] - sums[stack.peek()])) * nums[j]);
            } 
            // 新来的元素入栈
            stack.push(i);
        }
        // 最后将栈里剩余元素进行设置
        while (!stack.isEmpty()) {
            int j = stack.pop();
            // 当前栈中元素都不存在比他小的右边界，所以右边界从sums[size - 1]开始取
            max = Math.max(max, (stack.isEmpty() ? sums[size - 1] : (sums[size - 1] - sums[stack.peek()])) * arr[j]);
        }
        return max;
    }
}

柱状图中最大的矩形

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

image-20211215154559108

该问题即为上一题的具体形式，同样可以使用单调栈进行求解。