【力扣打卡系列】单调栈

坚持按题型打卡&刷&梳理力扣算法题系列，语言为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 就更新为去掉了最后一个字符的新字符串

原文地址：https://blog.csdn.net/qq_45734745/article/details/143581472

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！