首页 > 其他分享 >【力扣打卡系列】单调栈

【力扣打卡系列】单调栈

时间:2024-11-06 23:16:33浏览次数:3  
标签:int len st 力扣 temperatures ans 字符串 打卡 单调

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

标签:int,len,st,力扣,temperatures,ans,字符串,打卡,单调
From: https://blog.csdn.net/qq_45734745/article/details/143581472

相关文章

  • 【leetcode】40-best-time-to-buy-and-sell-stock 力扣 121. 买卖股票的最佳时机
    买卖股票系列【leetcode】40-best-time-to-buy-and-sell-stock力扣121.买卖股票的最佳时机【leetcode】41-best-time-to-buy-and-sell-stock-ii力扣122.买卖股票的最佳时机II【leetcode】42-best-time-to-buy-and-sell-stock-iii力扣123.买卖股票的最佳时机III【le......
  • SQL,力扣题目569,员工薪水中位数
    一、力扣链接LeetCode_569二、题目描述表: Employee+--------------+---------+|ColumnName|Type|+--------------+---------+|id|int||company|varchar||salary|int|+--------------+---------+id是该表的主......
  • 今日力扣:3254. 长度为 K 的子数组的能量值 I
    给你一个长度为 n 的整数数组 nums 和一个正整数 k 。一个数组的 能量值 定义为:如果 所有 元素都是依次 连续 且 上升 的,那么能量值为 最大 的元素。否则为-1。你需要求出 nums 中所有长度为 k 的 子数组 的能量值。请你返回一个长度为 n-k+......
  • 【java】实战-力扣题库:有序数组的平方
    问题描述给你一个按 非递减顺序 排序的整数数组 nums,返回 每个数字的平方 组成的新数组,要求也按 非递减顺序 排序。问题分析:既然给定的是一个非递减顺序的数组我们可以使用双指针,一个指向左边,一个指向右边,比较两边平方后的大小。哪个大,就把那个数放到当前数......
  • 代码随想录打卡Day14
    1.力扣226:翻转二叉树题目描述:给你一棵二叉树的根节点 root ,翻转这棵二叉树,并返回其根节点。示例1:输入:root=[4,2,7,1,3,6,9]输出:[4,7,2,9,6,3,1]示例2:输入:root=[2,1,3]输出:[2,3,1]示例3:输入:root=[]输出:[]解答代码:/***Definitionforabin......
  • 代码随想录打卡Day18
    1.二叉搜索树的最小绝对差:题目描述给你一个二叉搜索树的根节点 root ,返回 树中任意两不同节点值之间的最小差值 。差值是一个正数,其数值等于两值之差的绝对值。示例1:输入:root=[4,2,6,1,3]输出:1代码:/***Definitionforabinarytreenode.*structTree......
  • 代码随想录打卡Day17
    1.力扣954:最大二叉树:题目描述:给定一个不重复的整数数组 nums 。 最大二叉树 可以用下面的算法从 nums 递归地构建:创建一个根节点,其值为 nums 中的最大值。递归地在最大值 左边 的 子数组前缀上 构建左子树。递归地在最大值 右边 的 子数组后缀上 构建右......
  • 代码随想录打卡Day16
    1.力扣531:找树左下角的值。题目描述:给定一个二叉树的 根节点 root,请找出该二叉树的 最底层 最左边 节点的值。假设二叉树中至少有一个节点。示例1:输入:root=[2,1,3]输出:1示例2:输入:[1,2,3,4,null,5,6,null,null,7]输出:7解答代码:/***Defi......
  • 单调栈笔记
    单调栈笔记单调栈,顾名思义,就是把元素按照严格单调的顺序存在栈中(从「栈顶」到「栈底」)可以加速查找数组中满足特定条件的数的过程,例如:寻找左侧第一个比当前元素大的元素寻找左侧第一个比当前元素小的元素寻找右侧第一个比当前元素大的元素寻找右侧第一个比当前元素小的元素......
  • python+flask计算机毕业设计高校学生课堂考勤打卡APP的设计和实现(程序+开题+论文)
    本系统(程序+源码+数据库+调试部署+开发环境)带论文文档1万字以上,文末可获取,系统界面在最后面。系统程序文件列表开题报告内容一、选题背景关于高校学生课堂考勤的研究,现有研究多集中在传统点名方式的改进以及基于单一技术的考勤系统开发。例如,有的研究专注于利用蓝牙技术实......