首页 > 其他分享 >LeetCode239. 滑动窗口最大值(2024秋季每日一题 13)

LeetCode239. 滑动窗口最大值(2024秋季每日一题 13)

时间:2024-09-14 15:25:47浏览次数:15  
标签:13 窗口 nums 队列 元素 LeetCode239 2024 int 滑动


给你一个整数数组 nums,有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。

返回 滑动窗口中的最大值 。

示例 1:

输入:nums = [1,3,-1,-3,5,3,6,7], k = 3
输出:[3,3,5,5,6,7]
解释:

LeetCode239. 滑动窗口最大值(2024秋季每日一题 13)_算法

示例 2:

输入:nums = [1], k = 1
输出:[1]

提示:

LeetCode239. 滑动窗口最大值(2024秋季每日一题 13)_滑动窗口_02
LeetCode239. 滑动窗口最大值(2024秋季每日一题 13)_算法_03
LeetCode239. 滑动窗口最大值(2024秋季每日一题 13)_滑动窗口_04


思路:滑动窗口

  • 用队列维护一个窗口,队列内的元素从大到小排序
  • 每次动态的将当前元素加入到队列
  • 如果队列对头的元素时窗口大小为 k 的窗口外的,则将队头元素弹出队列
  • 假如当前元素大于等于队尾元素,则将队尾元素弹出,直到当前元素小于队尾元素,或者队列为空的时候,将当前元素加入到队尾(可以维护递减的队列,并且对于队尾元素,下标为 j,j 肯定 < i,如果 nums[j] <= nums[i],那么 nums[j] 就没必要存在于维护的这个滑动窗口中
class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        vector<int> res;
        int q[100010];
        memset(q, -1, sizeof q);
        int hh = 0, tt = -1;
        for(int i = 0; i < nums.size(); i++){
            while(hh <= tt && q[hh] <= i - k) hh++;
            while(hh <= tt && nums[q[tt]] <= nums[i]) tt--;
            q[++tt] = i;
            if(i >= k - 1) res.push_back(nums[q[hh]]);
        }
        return res;
    }
};


标签:13,窗口,nums,队列,元素,LeetCode239,2024,int,滑动
From: https://blog.51cto.com/u_15236041/12017109

相关文章

  • 2024年图纸加密软件最新版排行榜出炉!10款图纸加密软件大比拼
    随着企业和个人对信息安全的关注日益增加,图纸加密软件成为了保护机密数据的重要工具。无论是工程设计公司、建筑公司,还是制造业,都需要确保图纸文件的安全性,防止未经授权的访问和泄漏。2024年,一系列全新功能和技术的图纸加密软件登上了排行榜。本文将为您详细介绍排名前十的图......
  • RM1135、RM1135T量产修复成功,RTS5735DL量产工具操作教程,RTS5765DL、RTS5772DL开卡大致
    自己的固态坏了,本来打算找数据恢复公司恢复数据的,问了一下,大约需要上千块钱,算了,自己的数据还没这么值钱,于是就直接开卡了。这里把我自己研究的开卡方法分享给大家,注意开卡后硬盘数据会完全被擦除,不能恢复,所以有重要数据的话要提前备份!不好好看提示出了问题不要找我。开卡前必须准备......
  • 企业源代码怎么加密防泄密?2024十款好用的源代码加密软件
    在当今数字化和信息化的时代,企业的源代码通常承载了核心技术和商业机密,若被泄露或窃取,可能导致企业遭受不可估量的损失。为防止源代码泄密,企业需要采取多层次的安全措施,其中源代码加密是最关键的一环。1.安秉源代码加密安秉源代码加密软件是一款适用于Windows和Linux平台的......
  • 2024年PMP我可以自学通过考试吗?
    作为PMP考试的老考生,我想提醒一下,PMP考试费用很高,初次考试费用为3900元(重考费用为2500元)。如果你想自学PMP,一定要三思而后行。首先要问问自己是否符合以下几种情况:1.有相关的工作经验(项目经理/产品经理/技术岗),对项目管理的工作流程比较熟悉,这是一个优势。2.0基础,但学习能力......
  • 2024.9.12(周四)
    hadoop实现后台修改importorg.apache.hadoop.conf.Configuration;importorg.apache.hadoop.hbase.HBaseConfiguration;importorg.apache.hadoop.hbase.TableName;importorg.apache.hadoop.hbase.client.Connection;importorg.apache.hadoop.hbase.client.ConnectionFac......
  • 2024远程办公快速崛起,ToDesk抢先拿下上亿设备
    自2020年以来,在疫情影响下,远程办公正在进一步常态化渗透到各类企业中。根据公开数据,腾讯会议、飞书等线上协同软件月度活跃用户已突破千万级别,一场围绕”办公空间“的变革正在发生。在小编看来,远程移动办公给予企业和打工人更多机遇和挑战。对互联网软件企业而言,远程移动办公不......
  • 2024.9.11(周三)
    packagehadoop;importjava.io.IOException;importjava.util.StringTokenizer;importorg.apache.hadoop.conf.Configuration;importorg.apache.hadoop.fs.Path;importorg.apache.hadoop.io.IntWritable;importorg.apache.hadoop.io.Text;importorg.apache.hado......
  • 第131期 农业障碍物检测数据集
    引言亲爱的读者们,您是否在寻找某个特定的数据集,用于研究或项目实践?欢迎您在评论区留言,或者通过公众号私信告诉我,您想要的数据集的类型主题。小编会竭尽全力为您寻找,并在找到后第一时间与您分享。FieldSAFE——农业障碍物检测数据集一、背景随着农业现代化的不断推进,农业机械的......
  • 第132期 铁轨表面缺陷数据集(一)
    引言亲爱的读者们,您是否在寻找某个特定的数据集,用于研究或项目实践?欢迎您在评论区留言,或者通过公众号私信告诉我,您想要的数据集的类型主题。小编会竭尽全力为您寻找,并在找到后第一时间与您分享。探索RSDDs数据集:揭示铁轨表面缺陷的智能检测之旅在现代化的铁路运输体系中,铁轨作为......
  • 北京2024年下半年软考准考证打印时间11月5日开始
    根据2024下半年北京软考考务通知的说明,2024下半年北京软考准考证打印相关事项如下:一、2024下半年北京软考准考证打印时间2024年11月5日至11月8日。二、2024下半年北京软考准考证打印入口网址考生登录中国计算机技术职业资格网网上报名系统(http://www.ruankao.org.cn/),点击链接进入......