由于数据在栈内是单调递增或单调递减的，单调栈适合用来找出数组中第一个大于或小于某个元素的场景。元素出栈后，再根据题意对出栈元素进行处理，更新数据至result。
标准模板
- 第一个for循环内循环输入数组，
- 第二个for循环维持栈内单调特性，不满足单调的元素依次出栈
- 第一个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
| func nextGreaterElement(nums1 []int, nums2 []int) []int {
//单调递减栈
var stack,res []int
//标准模板，首个元素先入栈
stack = append(stack, 0)
//由于只需要输出num1的元素，构造nums1的map作为需要输出数据的查询
map1 := make(map[int]int)
for i,v := range(nums1) {
map1[v] = i
//顺便初始化res，查不到的为-1
res = append(res, -1)
}
for i:=1; i < len(nums2); i++ {
// 单调递减，所以>=的都出栈
for len(stack) > 0 && nums2[stack[len(stack)-1]] <= nums2[i] {
// 查表，需要输出的加入res
if idx, ok := map1[nums2[stack[len(stack)-1]]]; ok {
res[idx] = nums2[i]
}
//pop
stack = stack[:len(stack)-1]
}
// push
stack = append(stack, i)
}
return res
}
|
出栈后计算出栈元素高度所在层的面积
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
| /*
{2, 1, 0, 1, 3}
3
+---+
2 | |
+---+ + +
| 1 1 | |
+---+ +---+ +
| 0 | |
+---+ +
0 1 2 3 4
1. 按照下标0->1->2入栈
2. 下标3入栈前依次对2->1进行出栈，出栈结束后下标0还在栈内
a. 下标2出栈时，res += (min(height[3], height[1]) - height[2])*(3-1-1)
b. 下标1出栈时，res += (min(height[3], height[0]) - height[1])*(3-0-1)
3. 下标4入栈前依次对3进行出栈，res += (min(height[4], height[0]) - height[3])*(4-0-1)
res的加入是从右向左，按层的方式加入的
*/
// @lc code=start
func trap(height []int) int {
var stack []int
var res int
min := func(a, b int) int {
if a < b {
return a
}
return b
}
stack = append(stack, 0)
for i := 1; i < len(height); i++ {
for len(stack) > 0 && height[i] >= height[stack[len(stack)-1]] {
cachedTop := height[stack[len(stack)-1]]
stack = stack[:len(stack)-1]
if len(stack) == 0 {
break
}
res += (i - stack[len(stack)-1] - 1) * (min(height[i], height[stack[len(stack)-1]]) - cachedTop)
}
stack = append(stack, i)
}
return res
}
|
出栈后记录于外层循环中入栈元素下标的差值
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| func dailyTemperatures(temperatures []int) []int {
//由于最后求idx的距离，stack存下标
var stack []int
//res不是按顺序append的（出栈的顺序）
res := make([]int, len(temperatures))
stack = append(stack, 0)
for i:=1; i<len(temperatures);i++{
//一直出栈，直到栈空或满足单调递减了
//并做记录，写入res
for len(stack) > 0 && temperatures[i] > temperatures[stack[len(stack)-1]] {
//记录出栈的位置，值为新入栈的位置减去出栈的位置
res[stack[len(stack)-1]] = i - stack[len(stack)-1]
stack = stack[:len(stack)-1]
}
stack = append(stack, i)
}
//初始化时后面的数已经补零了
return res
}
|
与接雨水相反（接雨水算的是矩形外面的面积），这题算的是矩形的面积
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| func largestRectangleArea(heights []int) int {
max := func(a, b int) int {
if a > b {
return a
}
return b
}
heights = append([]int{0}, heights...)
heights = append(heights, 0)
var res int
//单调递增栈
var stack []int
stack = append(stack, 0)
for i := 1; i < len(heights); i++ {
for len(stack) > 0 && heights[i] < heights[stack[len(stack)-1]] {
res = max(res, (i-stack[len(stack)-2]-1)*heights[stack[len(stack)-1]])
stack = stack[:len(stack)-1]
}
stack = append(stack, i)
}
return res
}
|
子区间的最大值是单调递增的，因此栈保存每个子区间最大的元素值
- 新元素比栈顶元素大：入栈新区间
- 新元素比栈顶元素小：子区间最大值比新元素小的出栈（出栈的子区间合并到栈顶的子区间）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| func maxChunksToSorted(arr []int) int {
// 单调递增栈，存放各个子区间的最大值
var stack []int
stack = append(stack, arr[0])
for i := 1; i < len(arr); i++ {
if arr[i] > stack[len(stack)-1] {
//若新元素比栈顶元素大， 入栈新区间的最大值
stack = append(stack, arr[i])
} else {
//暂存最大的区间
mx := stack[len(stack)-1]
for len(stack) > 0 && arr[i] <= stack[len(stack)-1] {
stack = stack[:len(stack)-1]
}
//重新入栈这个区间的最大值
stack = append(stack, mx)
}
}
return len(stack)
}
|