algo-单调栈

介绍

源于栈结构,元素满足单调性:递增或者递减。

其应用的核心,笔者认为有点类似于不同身高的人站成一排,假设目光平视的话,队伍后面的人只能看到比自己身高要高(或相等)的人。由于遵循了栈的规范,操作只允许在栈顶。

插入操作

1
2
3
4
5
6
7
8
原先栈元素:
top-> [1,4,8,10,30]

欲插入 9,需要依次弹出 1,4,8,使得栈变成:
top-> [10,30]

插入后:
top-> [9,10,20]

代码模板:

1
2
3
4
5
6
7
8
9
void insert(x){
//maintain monopoly
while (!stack.isEmpty() && stack.top < x){
stack.pop()
//other process
}
//push new
  stack.push(x)
}

应用

LeetCode 上可以使用单调栈原理解决的问题很多,下面挑选几道比较有代表性的。

#496#next-greater-element-i

#496#next-greater-element-i

切题

题目给出两个数组,第一个数组是第二个的子集。求第一个数组的元素,在第二个数组中的下一个比较大的值。

我们可以只考虑第二个数组,那就是要求出元素看到的比自己大的元素。

可能解法

  • 单调栈 这个题目属于典型的单调栈题目,先把单调栈模板写上。
1
2
3
4
5
6
7
8
9
10
Stack stack = new Stack<>();
for (int i = n - 1; i >= 0; i--) {
int p = nums2[i];
while (!stack.empty() && stack.peek() < p){
stack.pop();
//process
}
//push
stack.push(p);
}

编码

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
public class Solution {

public int[] nextGreaterElement(int[] nums1, int[] nums2) {
if (nums1 == null || nums2 == null) return new int[]{};
int m = nums1.length;
int n = nums2.length;
//bad case
if (m > n) return new int[]{};

//only handle what we care
Map map = new HashMap<>();
for (int j : nums1) {
map.put(j, Integer.MIN_VALUE);
}

Stack stack = new Stack<>();
//lookback
for (int i = n - 1; i >= 0; i--) {
int p = nums2[i];
while (!stack.empty() && stack.peek() < p) stack.pop();
if (map.get(p) != null) {
map.put(p, stack.isEmpty() ? -1 : stack.peek());
}
stack.push(p);
}

int[] res = new int[m];
for (int i = 0; i < m; i++) {
res[i] = map.get(nums1[i]);
}

return res;
}
}

时间复杂度: 每个元素最多只入栈和出栈 1 次,O(N)

空间复杂度: 使用了栈和 Map 来保存临时数据,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
public static class TestPair<T_Input_1, T_Input_2, T_Expect, T_Target> {
final private T_Input_1 input1;
final private T_Input_2 input2;
final private T_Expect expect;
final private T_Target target;

public TestPair(T_Input_1 input1, T_Input_2 input2, T_Expect expect, T_Target target) {
this.input1 = input1;
this.input2 = input2;
this.expect = expect;
this.target = target;
}
}

public static void main(String[] args) {
Listint[], int[], int[], Integer>> tables = Arrays.asList(
new TestPair<>(new int[]{4, 1, 2}, new int[]{1, 3, 4, 2}, new int[]{-1, 3, -1}, null)
,
new TestPair<>(new int[]{2, 4}, new int[]{1, 2, 3, 4}, new int[]{3, -1}, null)
,//bad case #1
new TestPair<>(new int[]{}, new int[]{1, 2, 3, 4}, new int[]{}, null)
,//bad case #2
new TestPair<>(new int[]{1, 2}, new int[]{}, new int[]{}, null)
);

for (TestPair<int[], int[], int[], Integer> p : tables) {
Assert.assertEquals(Arrays.toString(p.expect), Arrays.toString(new Solution().nextGreaterElementV0(p.input1, p.input2)));
}
}

#504#next-greater-element-ii

#504#next-greater-element-ii

与上题类似,变化是数组环形首位相接,所以一个数字,要考虑自己后方前方的数字。只需要把入栈的元素增加一倍,对序号取模操作即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public int[] nextGreaterElements(int[] nums) {
if (nums == null || nums.length == 0) return new int[]{};
int m = nums.length;

int[] res = new int[m];
Stack stack = new Stack<>();
for (int i = 2 * m - 1; i >= 0; i--) {
int p = nums[i % m];
while (!stack.empty() && stack.peek() <= p) stack.pop();

res[i % m] = stack.empty() ? -1 : stack.peek();
stack.push(p);
}

return res;
}

#42#trapping-rain-water

#42#trapping-rain-water

切题

题目给出的图,很好的说明了题意。

可能解法

本题可以:

1)暴力

2)动态规划

3)双指针

4)单调栈

本文只介绍单调栈。

模板先写上:

1
2
3
4
5
6
7
8
9
10
11
int current = 0;
Stack stack = new Stack<>();
while (current < len) {
//handle smaller
while (!stack.isEmpty() && height[stack.peek()] < height[current]) {
int p = stack.pop();
//process
}
//push
stack.push(current++);
}

在使用单调栈的时候,核心是分层考虑形成的凹槽。

levels

编码

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
public class Solution {
/**
* lookback, tap water by the vertical level
*
* @param height
* @return
*/
public int trap(int[] height) {
if (height == null) return 0;
int len = height.length;
if (len == 0) return 0;

int amount = 0, current = 0;
Stack stack = new Stack<>();
while (current < len) {
//handle smaller
while (!stack.isEmpty() && height[stack.peek()] < height[current]) {
int popHeight = height[stack.pop()];
if (stack.isEmpty()) break;

int distance = current - stack.peek() - 1;
int heightDiff = Math.min(height[current], height[stack.peek()]) - popHeight;
amount += distance * heightDiff;
}
//push
stack.push(current++);
}
return amount;
}
}

时间复杂度: 每个元素最多只入栈和出栈 1 次,O(N)

空间复杂度: 使用了栈和保存临时数据,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
public static class TestPair {
final private T_Input_1 input1;
final private T_Input_2 input2;
final private T_Expect expect;
final private T_Target target;

public TestPair(T_Input_1 input1, T_Input_2 input2, T_Expect expect, T_Target target) {
this.input1 = input1;
this.input2 = input2;
this.expect = expect;
this.target = target;
}
}

public static void main(String[] args) {
List> tables = Arrays.asList(
new TestPair<>(new int[]{0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1}, null, 6, null)
,
new TestPair<>(new int[]{}, null, 0, null)
);

for (TestPair p : tables) {
Assert.assertEquals((long) p.expect, new Solution().trap(p.input1));
}
}

总结

从以上例子可以看到,单调栈的核心在于插入新元素前:

1)栈顶较小元素出栈

该操作维持栈的单调性。

2)根据出栈元素、栈顶元素、当前元素的关系进行处理

参考链接

https://oi-wiki.org/ds/monotonous-stack/

https://labuladong.gitbook.io/algo/shu-ju-jie-gou-xi-lie/dan-tiao-zhan

相关文章推荐