坚持按题型打卡&刷&梳理力扣算法题系列,语言为go,Day20
单调栈
- 题目描述
- 解题思路
- 单调栈
- 后进先出
- 记录的数据加在最上面
- 丢掉数据也先从最上面开始
- 单调性
- 记录t[i]之前会先把所有小于等于t[i]的数据丢掉,不可能出现上面大下面小的情况
- 倒着遍历,while遍历,遇到小的就pop,然后把当前值加进去,栈顶即为最近的大于当前i值对应的数,要存的值就是st[-1]-i
- 优化的地方:每次拿到元素时就应该和栈顶元素进行比较,直到栈空或者扫描结束
- 思想:及时去掉无用的数据,保证栈内数据的有序
- 后进先出
- 单调栈
- 代码参考
func dailyTemperatures(temperatures []int) []int {
ans := make([]int,len(temperatures))
st := []int{}
for i,j := range slices.Backward(temperatures){
for len(st) > 0 && j>=temperatures[st[len(st)-1]]{ //注意此处是大于等于
st = st[:len(st)-1]
}
if len(st) > 0{
ans[i] = st[len(st)-1] - i
}
st =append(st,i)
}
return ans
}
- tips
- 注意倒序遍历的写法:for i,j := range slices.Backward(temperatures)
- 将ans定义为一个定长切片:ans := make([]int,len(temperatures))
- st = st[:len(st)-1]
st[:len(st)-1]
是对字符串st
进行切片操作,它取从字符串开始到长度减去1的位置的子字符串。切片操作在 Go 语言中是通过字符串[开始索引:结束索引]
来实现的。st = st[:len(st)-1]
将切片操作的结果重新赋值给变量st
,这样st
就更新为去掉了最后一个字符的新字符串