
739. 每日温度 - 力扣(LeetCode)


栈里边存放的是还没有找到后边更大值的元素
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
| func dailyTemperatures(temperatures []int) []int { length := len(temperatures) ans := make([]int, length) stack := []int{} for i := 0; i < length; i ++ { temperature := temperatures[i] fmt.Println("temperature:", temperature) fmt.Println("stack:", stack) for len(stack) > 0 && temperature > temperatures[stack[len(stack) -1]] { fmt.Println("temperature now:", temperature, temperatures[stack[len(stack) -1]], stack[len(stack) -1]) preindex := stack[len(stack)-1] stack = stack[:len(stack) -1] ans[preindex] = i -preindex } stack = append(stack, i) } return ans }
func dailyTemperatures(temperatures []int) []int { lens := len(temperatures) ans := make([]int, lens) stack := []int{} for i := lens-1; i >= 0; i-- { temperature := temperatures[i] for len(stack) > 0 && temperature >= temperatures[stack[len(stack)-1]] { stack = stack[:len(stack)-1] } if len(stack) > 0 { ans[i] = stack[len(stack)-1] - i } stack = append(stack, i) } return ans }
|


单调栈 适用于 上一个更大(更小)元素,或者下一个更大(小)元素
这段代码是一个Go语言编写的函数,名为dailyTemperatures
,它使用单调栈的数据结构来解决一个特定问题:给定一个每日温度列表temperatures
,返回一个新列表,其中第i个元素是温度列表中第i天之后第一个比第i天温度更高的温度的天数。
代码思想解释:
问题定义:我们想要找到一个序列中每个元素之后的第一个更大元素,并记录它们之间的索引差。
单调栈的应用:单调栈是一种特殊的栈结构,它保证栈内的元素是单调递增或单调递减的。在这个场景中,我们使用单调栈来维护一个索引栈,栈内元素代表尚未找到更大温度的天的索引。
初始化:
n
:记录输入温度数组的长度。ans
:初始化一个长度为n
的数组,用于存储结果,初始值设为0。st
:初始化一个空的切片,用作单调栈。
遍历温度数组:
- 通过
range
关键字遍历temperatures
数组,同时获取索引i
和对应的温度值t
。
维护单调栈:
- 当前温度
t
大于栈顶元素对应的温度时,说明栈顶元素之后的第一个更高温度就是当前温度。此时,执行以下操作:- 弹出栈顶元素
j
,即st[len(st)-1]
。 - 计算索引差
i - j
,并将这个差值赋给ans[j]
。 - 更新栈
st
,移除栈顶元素。
压栈操作:
- 将当前索引
i
压入栈st
中。这表示当前索引的天还没有找到之后的第一个更高温度。
返回结果:
- 遍历结束后,返回
ans
数组,其中每个元素表示对应天之后第一个更高温度的天数。
接雨水
42. 接雨水 - 力扣(LeetCode)


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
| func trap(height []int) (ans int) { st := []int{} for i, h := range height { for len(st) > 0 && h >= height[st[len(st)-1]] { %% - 当遇到相等高度的柱子时,后面的柱子才是有效的右边界 - 使用`>=`可以正确处理这种情况,确保弹出所有小于等于当前高度的柱子 - 如果只用`>`,相等高度的柱子会留在栈中,导致计算错误 %% bottomH := height[st[len(st)-1]] st = st[:len(st)-1] if len(st) == 0 { break } left := st[len(st)-1] dh := min(height[left], h) - bottomH ans += dh * (i - left - 1) } st = append(st, i) } return }
## 示例分析
以高度数组`[0,1,0,2,1,0,1,3,2,1,2,1]`为例:
1. 遇到第二个高度为1的柱子时: - 弹出之前高度为0的柱子 - 计算它与左边高度1的柱子之间的雨水 2. 遇到高度为2的柱子时: - 弹出高度为1的柱子(因为2 >= 1) - 计算它与左边更高柱子之间的雨水 3. 遇到相等高度1的柱子时: - 前面的1被弹出(因为1 >= 1) - 确保新的1作为右边界参与后续计算
|
单调队列
239. 滑动窗口最大值
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
| func maxSlidingWindow(nums []int, k int) []int { ans := make([]int, 0, len(nums)-k+1) q := []int{} for i, x := range nums { for len(q) > 0 && x >= nums[q[len(q)-1]] { q = q[:len(q)-1] } q = append(q, i)
if q[0] <= i -k{ q = q[1:] }
if i >= k-1 { ans = append(ans, nums[q[0]]) } } return ans }
|
从「维护单调性」的角度上来说,单调队列和单调栈是一样的,一个弹出队尾元素,另一个弹出栈顶元素。在单调栈的基础上,单调队列多了一个「移除队首」的操作,这类似滑动窗口移动左指针 left 的过程。所以从某种程度上来说,单调队列 = 单调栈 + 滑动窗口。
