理论基础
单调栈适合于找第一个比当前元素大或者小的
栈里放元素下标
栈顶到栈底递增：求第一个比当前元素大的；栈顶到栈底递减：求第一个比当前元素小的
求第一个比当前元素大的工作过程：遍历数组
- 当前遍历元素比栈顶大：找到了第一个比栈顶元素大的，用一个新数组记录下来，新数组的下标用当前栈顶保存的下标，值若是求距离的话就用当前遍历元素下标减去栈顶保存的下标；弹出栈顶下标，继续比较，直到当前元素比栈顶元素小时则入栈；
- 当前遍历元素比栈顶小：直接入栈
- 当前遍历元素等于栈顶：题目是求大于，则直接入栈；若题目是求大于等于则记录、弹栈、入栈
- 最后栈中剩下的说明没有比它大的元素
单调栈的本质是空间换时间，因为在遍历的过程中需要用一个栈来记录右边第一个比当前元素高的元素，优点是整个数组只需要遍历一次。
更直白来说，就是用一个栈来记录我们遍历过的元素，因为我们遍历数组的时候，我们不知道之前都遍历了哪些元素，以至于遍历一个元素找不到是不是之前遍历过一个更小的，所以我们需要用一个容器（这里用单调栈）来记录我们遍历过的元素。
每日温度
739. 每日温度 - 力扣（LeetCode）
给定一个数组，每个元素表示每天的温度，返回一个数组，每个元素表示比该天温度高的下一温度出现在第几天，若没有则为0
暴力超时：两层for循环，外层i循环遍历每天温度，内层j从i+1开始循环从找高温，时间复杂度O(n2)
单调栈：求第一个比当前元素大的元素的距离，时间复杂度为O(n)
- 定义一个结果数组；go中用切片模拟栈，
push：append, pop:[:len(stack)-1]
- 进入循环前将下标0元素入栈；外层for循环从下标1遍历给定数组；遇到比栈顶小或等于的入栈；否则进入内层循环(go中用for省略前后替代while)，若栈非空且比栈顶大，则记录（结果集的下标用栈顶下标）、弹栈；内层循环结束后当前元素下标入栈
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
func dailyTemperatures(temperatures []int) []int {
res := make([]int, len(temperatures))
stack := make([]int, 0)
stack = append(stack, 0)
for i := 1; i < len(temperatures); i++ {
if temperatures[i] <= temperatures[stack[len(stack)-1]] {
stack = append(stack, i)
} else {
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
}
|
精简版：用for range从首遍历，内层若栈非空且比栈顶大，则记录、弹栈；内层循环结束后当前元素下标入栈
1
2
3
4
5
6
7
8
9
10
11
12
|
func dailyTemperatures(temperatures []int) []int {
res := make([]int, len(temperatures))
stack := make([]int, 0)
for i, v := range temperatures {
for len(stack) != 0 && v > 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
}
|
下一个更大元素 I
496. 下一个更大元素 I - 力扣（LeetCode）
给定两个整数数组nums1和nums2，nums1是nums2的子集，求nums1中每个元素值在nums2中对应元素值右侧第一个比该元素值大的元素值，若没有比该元素值大的则为-1
结果数组初始化长度为nums1长度，值全为-1
map映射：遍历nums1；元素值作为K，下标作为V
单调栈：遍历nums2；若当前元素比栈顶元素小或等于，则入栈；若当前元素比栈顶元素大，判断在map中能否找到栈顶元素的映射，能找到则记录（map中v作为结果数组下标，当前元素值作为结果数组值）、弹栈、循环比较、入栈，不能找到映射则弹栈、循环比较、入栈
本题由于有map保存栈中元素的下标，所以可以直接用栈保存值，建议以后还是用栈保存下标，更通用
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
|
func nextGreaterElement(nums1 []int, nums2 []int) []int {
res := make([]int, len(nums1))
for i := range res {
res[i] = -1
}
mapping := make(map[int]int)
for i := range nums1 {
mapping[nums1[i]] = i
}
stack := make([]int, 0)
stack = append(stack, nums2[0])
for i := 1; i < len(nums2); i++ {
if nums2[i] <= stack[len(stack)-1] {
stack = append(stack, nums2[i])
} else {
for len(stack) != 0 && nums2[i] > stack[len(stack)-1] {
if v, ok := mapping[stack[len(stack)-1]]; ok {
res[v] = nums2[i]
}
stack = stack[:len(stack)-1]
}
stack = append(stack, nums2[i])
}
}
return res
}
|
精简版：用for range从首遍历，内层若栈非空且比栈顶大，则记录、弹栈；内层循环结束后当前元素入栈
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
func nextGreaterElement(nums1 []int, nums2 []int) []int {
res := make([]int, len(nums1))
stack := make([]int, 0)
mapping := make(map[int]int)
for i := range res {
res[i] = -1
}
for i, v := range nums1 {
mapping[v] = i
}
for _, cur := range nums2 {
for len(stack) != 0 && cur > stack[len(stack)-1] {
if v, ok := mapping[stack[len(stack)-1]]; ok {
res[v] = cur
}
stack = stack[:len(stack)-1]
}
stack = append(stack, cur)
}
return res
}
|
下一个更大元素 II
503. 下一个更大元素 II - 力扣（LeetCode）
给定一个循环数组，返回数组中每个元素的下一个比它大的元素，没找到就是-1
循环遍历也就是从当前元素开始向后遍历到尾后，再从首开始向后遍历到当前元素，即遍历两遍该数组
思路一：用两个数组拼接后的新数组模拟成环遍历，结果集初始化为新数组长度，最后返回结果集的前半部分
思路二：遍历次数为二倍数组长度，循环变量取模，下标对数组长度取模
注意：go中追加切片时需要将切片用...打散
思路一：构建新数组
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
func nextGreaterElements(nums []int) []int {
nums = append(nums, nums...)
res := make([]int, len(nums))
stack := make([]int, 0)
for i := range res {
res[i] = -1
}
stack = append(stack, 0)
for i := 1; i < len(nums); i++ {
if nums[i] <= nums[stack[len(stack)-1]] {
stack = append(stack, i)
} else {
for len(stack) != 0 && nums[i] > nums[stack[len(stack)-1]] {
res[stack[len(stack)-1]] = nums[i]
stack = stack[:len(stack)-1]
}
stack = append(stack, i)
}
}
return res[:len(res)/2]
}
|
思路一精简版：for range，省略小于等于
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
func nextGreaterElements(nums []int) []int {
nums = append(nums, nums...)
res := make([]int, len(nums))
stack := make([]int, 0)
for i := range res {
res[i] = -1
}
for i, cur := range nums {
for len(stack) != 0 && cur > nums[stack[len(stack)-1]] {
res[stack[len(stack)-1]] = cur
stack = stack[:len(stack)-1]
}
stack = append(stack, i)
}
return res[:len(res)/2]
}
|
思路二：取模
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
func nextGreaterElements(nums []int) []int {
res := make([]int, len(nums))
stack := make([]int, 0)
for i := range res {
res[i] = -1
}
stack = append(stack, 0)
for i := 1; i < len(nums)*2; i++ {
if nums[i%len(nums)] <= nums[stack[len(stack)-1]] {
stack = append(stack, i%len(nums))
} else {
for len(stack) != 0 && nums[i%len(nums)] > nums[stack[len(stack)-1]] {
res[stack[len(stack)-1]] = nums[i%len(nums)]
stack = stack[:len(stack)-1]
}
stack = append(stack, i%len(nums))
}
}
return res
}
|
接雨水
42. 接雨水 - 力扣（LeetCode）
给定一个整数数组，表示横轴上每个宽度为一的柱子的高度，雨水从上落下，返回这些柱子之间的凹槽能接到的最大雨水量，纵轴不算柱子，可以落到横轴上
遍历柱子，求出每个柱子左边和右边第一个比它高的柱子的高度
- 栈顶下标元素的柱子的凹槽能接的雨水量的高度 = min（左柱子高度，右柱子高度）- 栈顶下标元素的柱子高度；
- 栈顶下标元素的柱子的凹槽能接的雨水量的宽度 = 右柱子下标 - 左柱子下标 - 1
若当前元素大于栈顶下标元素，则说明当前元素是栈顶下标元素右边第一个比它大的元素，栈顶下标元素的下一个下标元素是栈顶下标元素左边第一个大于等于它的元素；记录栈顶元素、弹栈、记录栈顶元素，计算雨水面积、入栈
若当前元素等于栈顶下标元素，直接入栈，后面遍历到比栈顶元素大的元素时，栈顶下标元素=栈顶下一个下标元素，则左柱子高度一定是最小的柱子高度，再减去栈顶下标元素的柱子高度，得出栈顶下标元素的柱子的凹槽高度为0；出栈后再比较当前元素和栈顶下标元素（也就是刚才的左柱子高度），现在的高度就不是0了，宽度也包括刚才的栈顶下标元素的柱子宽度
单调栈是横向从下往上求雨水面积，可以用62213来模拟过程
注意：一旦有弹栈、后面对栈操作前就要判断栈非空
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
|
func trap(height []int) int {
res := 0
stack := make([]int, 0)
stack = append(stack, 0)
for i := 1; i < len(height); i++ {
if height[i] <= height[stack[len(stack)-1]] {
stack = append(stack, i)
} else {
for len(stack) != 0 && height[i] > height[stack[len(stack)-1]] {
mid := height[stack[len(stack)-1]]
stack = stack[:len(stack)-1]
if len(stack) != 0 {
h := min(height[i], height[stack[len(stack)-1]]) - mid
w := i - stack[len(stack)-1] - 1
res += h * w
}
}
stack = append(stack, i)
}
}
return res
}
|
精简版：for range，省略小于等于
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
func trap(height []int) int {
res := 0
stack := make([]int, 0)
for i, v := range height {
for len(stack) != 0 && v > height[stack[len(stack)-1]] {
mid := height[stack[len(stack)-1]]
stack = stack[:len(stack)-1]
if len(stack) != 0 {
h := min(v, height[stack[len(stack)-1]]) - mid
w := i - stack[len(stack)-1] - 1
res += h * w
}
}
stack = append(stack, i)
}
return res
}
|
柱状图中最大的矩形
84. 柱状图中最大的矩形 - 力扣（LeetCode）
给定一个整数数组，数组中各个元素表示柱状图中各个柱子的高度，每个柱子彼此相邻且宽度为 1 ，求在该柱状图中，能够勾勒出来的矩形的最大面积，可以是多个相邻柱子组成的矩形面积，也可以是单个柱子面积
遍历柱子，找左右比它矮的第一个柱子，若相邻则说明无法向该方向平移扩展该柱子的面积，若不相邻则说明可以向该方向平移扩展该柱子的面积，平移扩展到比该柱子矮的第一个柱子前一个柱子的位置。
总结：每一个柱子都去找左右边比它矮的第一个柱子来确定宽，再用该柱子的高乘以宽，就能算出该柱子所能形成的最大矩形面积，最后返回一个最大的即可
单调栈：若当前元素大于等于栈顶元素，则入栈；若当前元素小于栈顶元素，则当前元素是栈顶元素右边第一个比它小的元素，记录栈顶元素后出栈，新栈顶元素是上一个出栈元素的左边第一个小于等于它的元素
- 矩形宽 = 右边柱子下标 - 左边柱子下标 - 1
- 矩形高 = 栈顶柱子高
本题需要给原数组首尾加0，给尾加0避免给定数组递增，导致一直没有出栈计算的过程；给首加0避免给定数组递减，导致一直没有出栈计算的过程
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
func largestRectangleArea(heights []int) int {
res := 0
heights = append([]int{0}, heights...)
heights = append(heights, 0)
stack := make([]int, 0)
stack = append(stack, 0)
for i := 1; i < len(heights); i++ {
if heights[i] >= heights[stack[len(stack)-1]] {
stack = append(stack, i)
} else {
for len(stack) != 0 && heights[i] < heights[stack[len(stack)-1]] {
mid := heights[stack[len(stack)-1]]
stack = stack[:len(stack)-1]
if len(stack) != 0 {
w := i - stack[len(stack)-1] - 1
res = max(res, w*mid)
}
}
stack = append(stack, i)
}
}
return res
}
|
精简版：for range，省略小于等于
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
func largestRectangleArea(heights []int) int {
res := 0
heights = append([]int{0}, heights...)
heights = append(heights, 0)
stack := make([]int, 0)
for i, v := range heights {
for len(stack) != 0 && v < heights[stack[len(stack)-1]] {
mid := heights[stack[len(stack)-1]]
stack = stack[:len(stack)-1]
if len(stack) != 0 {
w := i - stack[len(stack)-1] - 1
res = max(res, w*mid)
}
}
stack = append(stack, i)
}
return res
}
|