首页 > 其他分享 >Leecode 滑动窗口最大值

Leecode 滑动窗口最大值

时间:2024-09-21 13:55:15浏览次数:12  
标签:nums 队列 最大值 queue int Leecode result 队尾值 滑动

 使用了双向链表

输入: nums = [1,3,-1,-3,5,3,6,7], 和 k = 3 输出: [3,3,5,5,6,7] 解释过程中队列中都是具体的值,方便理解,具体见代码。

初始状态:L=R=0,队列:{}

i=0,nums[0]=1。队列为空,直接加入。队列:{1}

i=1,nums[1]=3。队尾值为1,3>1,弹出队尾值,加入3。队列:{3}

i=2,nums[2]=-1。队尾值为3,-1<3,直接加入。队列:{3,-1}。此时窗口已经形成,L=0,R=2,result=[3]

i=3,nums[3]=-3。队尾值为-1,-3<-1,直接加入。队列:{3,-1,-3}。队首3对应的下标为1,L=1,R=3,有效。result=[3,3]

i=4,nums[4]=5。队尾值为-3,5>-3,依次弹出后加入。队列:{5}。此时L=2,R=4,有效。result=[3,3,5]

i=5,nums[5]=3。队尾值为5,3<5,直接加入。队列:{5,3}。此时L=3,R=5,有效。result=[3,3,5,5]

i=6,nums[6]=6。队尾值为3,6>3,依次弹出后加入。队列:{6}。此时L=4,R=6,有效。result=[3,3,5,5,6]

i=7,nums[7]=7。队尾值为6,7>6,弹出队尾值后加入。队列:{7}。此时L=5,R=7,有效。result=[3,3,5,5,6,7] 

代码参考了leecod评论里的代码

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        if(nums == null || nums.length < 2) return nums;
        // 双向队列 保存当前窗口最大值的数组位置 保证队列中数组位置的数值按从大到小排序
        LinkedList<Integer> queue = new LinkedList();
        // 结果数组
        int[] result = new int[nums.length-k+1];
        // 遍历nums数组
        for(int i = 0;i < nums.length;i++){
            // 保证从大到小 如果前面数小则需要依次弹出,直至满足要求
            while(!queue.isEmpty() && nums[queue.peekLast()] <= nums[i]){
                queue.pollLast();
            }
            // 添加当前值对应的数组下标
            queue.addLast(i);
            // 判断当前队列中队首的值是否有效
            if(queue.peek() <= i-k){
                queue.poll();   
            } 
            // 当窗口长度为k时 保存当前窗口中最大值
            if(i+1 >= k){
                result[i+1-k] = nums[queue.peek()];
            }
        }
        return result;
    }
}

作者:废物也听歌
链接:https://leetcode.cn/problems/sliding-window-maximum/solutions/10025/shuang-xiang-dui-lie-jie-jue-hua-dong-chuang-kou-2/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

标签:nums,队列,最大值,queue,int,Leecode,result,队尾值,滑动
From: https://blog.csdn.net/weixin_51161807/article/details/142385831

相关文章

  • JavaScript 中平滑动画的秘密!
    想要在您的网络应用程序中创建黄油般平滑的动画吗?尝试requestanimationframe——javascript的内置优化动画方法!requestanimationframe不使用settimeout或setinterval(这可能会因帧速率不一致而导致动画卡顿),而是将动画与浏览器的刷新率同步,以获得最佳性能。使用方法如下:letp......
  • 【力扣刷题】2090.半径为k的子数组平均值(定长滑动窗口)
    题目:给你一个下标从 0 开始的数组 nums ,数组中有 n 个整数,另给你一个整数 k 。半径为k的子数组平均值 是指:nums 中一个以下标 i 为 中心 且 半径 为 k 的子数组中所有元素的平均值,即下标在 i-k 和 i+k 范围(含 i-k 和 i+k)内所有元素的平均......
  • JavaScript(单分支语句,双分支语句,多分支语句判断闰年还是平年,三元运算符求最大值,switch
    <!DOCTYPEhtml><htmllang="en"><head><metacharset="UTF-8"><metaname="viewport"content="width=device-width,initial-scale=1.0"><title>Document</title><......
  • 1749. 任意子数组和的绝对值的最大值
    题目链接1749.任意子数组和的绝对值的最大值思路前缀和/动态规划-最大子数组和-简单变体题解链接两种方法:动态规划/前缀和(附题单!Python/Java/C++/Go/JS)关键点无时间复杂度\(O(n)\)空间复杂度\(O(1)\)代码实现(动态规划):classSolution:defmax......
  • LeeCode打卡第二十八天
    LeeCode打卡第二十八天第一题:路径总和II(LeeCode第437题):给定一个二叉树的根节点root,和一个整数targetSum,求该二叉树里节点值之和等于targetSum的路径的数目。路径不需要从根节点开始,也不需要在叶子节点结束,但是路径方向必须是向下的(只能从父节点到子节点)。解法......
  • 【视频教程】手把手AppWizard轻松制作一个emWin滑动主界面控制框架,任意跳转控制(2024-0
    现在的新版AppWizard已经比较好用,用户可以轻松的创建各种项目常规界面。比如早期创建一个支持滑动的主界面框架,并且可以跳转各种子界面,仅仅界面布局和各种图片格式转换都要花不少时间,而现在使用AppWizard,可以说轻轻松松,毫不费力。用户唯一要做的就是根据自己的芯片性能做一定的速度......
  • 【Android】ToolBar,滑动菜单,悬浮按钮和可交互提示等的使用方法
    ToolBarToolbar的强大之处在于,它不仅继承了ActionBar的所有功能,而且灵活性很高,可以配合其他控件来完成一些MaterialDesign的效果。任何一个新建的项目,默认都是会显示ActionBar。可以打开AndroidManifest看一下:<?xmlversion="1.0"encoding="utf-8"?><manifestxmlns......
  • 【高中数学/三角函数】设x,y为实数,若4x^2+y^2+xy=1,求2x+y的最大值?
    【问题】设x,y为实数,若4x^2+y^2+xy=1,求2x+y的最大值?【出处】《解题卡壳怎么办--高中数学解题智慧剖析》P38页第8题首问余继光、苏德矿著 【解答】由4x^2+y^2+xy=1配方得(2x+y/4)^2+15/16*y^2=1可设2x+y/4=cosθ,根号15/4*y=sinθ于是2x+y=cosθ-sinθ+4sinθ/根号15=2*根号10/5*s......
  • Swift里的数值变量的最大值和最小值
    Swift里有很多种数值变量,如Int,Int8,Float,Double等。和绝大多数编程语言一样,由于是在计算机上运行,内存有限,所以必有最大值和最小值,而计算机无法处理超过该值的数。在Swift中,数字变量类型都有一些静态属性,其固定值为该类变量的最大值和最小值。一、整数型变量(一)如何找到最大值......
  • 【高中数学/最值/基本不等式】已知x>0,y>0,且x+y=7,则(1+x)(2+y)的最大值为?
    【题目】已知x>0,y>0,且x+y=7,则(1+x)(2+y)的最大值为?(湖南雅礼中学高三阶段练习)【出处】《高考数学极致解题大招》P99典例1-2中原教研工作室编著【解答一:二次函数法】(1+x)(2+y)=9+x(1+y)=9+x(8-x)=-x^2+8x+9=-(x-4)^2+25故当x=4时,上式最大值取25,此时y=3【解答二:基本不等式法】由......