当前位置: 首页 > news >正文

【二叉树】【单调双向队列】LeetCode239:滑动窗口最大值

作者推荐

map|动态规划|单调栈|LeetCode975:奇偶跳

涉及知识点

单调双向队列 二叉树

题目

给你一个整数数组 nums,有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
返回 滑动窗口中的最大值 。
示例 1:
输入:nums = [1,3,-1,-3,5,3,6,7], k = 3
输出:[3,3,5,5,6,7]
解释:
滑动窗口的位置 最大值


[1 3 -1] -3 5 3 6 7 3
1 [3 -1 -3] 5 3 6 7 3
1 3 [-1 -3 5] 3 6 7 5
1 3 -1 [-3 5 3] 6 7 5
1 3 -1 -3 [5 3 6] 7 6
1 3 -1 -3 5 [3 6 7] 7
示例 2:
输入:nums = [1], k = 1
输出:[1]
参数范围
1 <= nums.length <= 105
-104 <= nums[i] <= 104
1 <= k <= nums.length

单调栈

时间复杂度😮(n)。
queMax中记录(i-k,i],如果i1 < i2,且nums[i1] <=nums[i2],那么i1无论如何都无法成为最大值。故可以淘汰i1,淘汰i1后,成降序排列。队首元素最大。
对queMax有三种操作。

操作一队尾淘汰i1
操作二队尾插入i2
操作三队首删除i-k,由于操作二,queMax不会为空,所以无需判断是否为空。如果i-k已经被操作一淘汰,则不能删除。

代码

核心代码

class Solution {
public:vector<int> maxSlidingWindow(vector<int>& nums, int k) {int i = 0;std::deque<int> queMax;vector<int> vRet;for ( i = 0; i < k; i++){while (queMax.size() && (nums[queMax.back()] <= nums[i])){queMax.pop_back();}queMax.emplace_back(i);			}vRet.emplace_back(nums[queMax.front()]);for (; i < nums.size(); i++){if (i - k == queMax.front()){queMax.pop_front();}while (queMax.size() && (nums[queMax.back()] <= nums[i])){queMax.pop_back();}queMax.emplace_back(i);vRet.emplace_back(nums[queMax.front()]);}return vRet;}
};

测试用例

template<class T>
void Assert(const T& t1, const T& t2)
{assert(t1 == t2);
}template<class T>
void Assert(const vector<T>& v1, const vector<T>& v2)
{if (v1.size() != v2.size()){assert(false);return;}for (int i = 0; i < v1.size(); i++){Assert(v1[i], v2[i]);}
}int main()
{vector<int> nums;int k;{Solution sln;nums = { 1, 3, -1, -3, 5, 3, 6, 7 }, k = 3;auto res = sln.maxSlidingWindow(nums, k);Assert(vector<int>{ 3,3,5,5,6,7 }, res);}{Solution sln;nums = { 1 }, k = 1;auto res = sln.maxSlidingWindow(nums, k);Assert(vector<int>{ 1 }, res);}//CConsole::Out(res);
}

2023年3月二叉树

用多键二叉树(红黑树)mulset记录滑动窗口中的数,由于二叉树默认是升序排列,所以最后一个元素,就是最大值。由于二叉树的插入、删除的时间复杂度是O(logn),故总时间复杂度是O(nlogn)

 class Solution {public:vector<int> maxSlidingWindow(vector<int>& nums, int k) {int i = 0;std::multiset<int> setNums;for (; i + 1 < k; i++){setNums.insert(nums[i]);}vector<int> vRet;for (; i < nums.size(); i++){setNums.insert(nums[i]);vRet.push_back(*setNums.rbegin());auto it = setNums.find(nums[i + 1 - k]);setNums.erase(it);}return vRet;}};

2023年3月第二版

class Solution {
public:
vector maxSlidingWindow(vector& nums, int k) {
vector<pair<int, int>> vValueIndex;
vector vRet;
int iPos = 0;
for (int i = 0; i < nums.size(); i++)
{
while ( ( vValueIndex.size() > iPos ) && (nums[i] >= vValueIndex.back().first))
{
vValueIndex.pop_back();
}
vValueIndex.emplace_back(nums[i], i);
if (i + 1 >= k)
{
vRet.push_back(vValueIndex[iPos].first);
}
if (i + 1 - k == vValueIndex[iPos].second)
{
iPos++;
}
}
return vRet;
}
};

2023年8月版

class Solution{
public:
vector maxSlidingWindow(vector&nums, int k) {
m_c = nums.size();
//每k个元素用一组,vLeft各元素到组首的最大值,vRight各元素到组尾的最大值
vector vLeft(m_c), vRight(m_c);
int iMax = 0;
for (int i = 0; i < m_c; i++)
{
if (0 == i % k)
{
iMax = nums[i];
}
else
{
iMax = max(iMax, nums[i]);
}
vLeft[i] = iMax;
}
iMax = -100 * 1000;
for (int i = m_c-1;i >= 0 ; i-- )
{
if (0 == (i+1) % k)
{
iMax = nums[i];
}
else
{
iMax = max(iMax, nums[i]);
}
vRight[i] = iMax;
}
vector vRet;
for (int i = k-1; i < m_c; i++)
{
vRet.emplace_back( max(vRight[i-k+1], vLeft[i]));
}
return vRet;
}
int m_c;
};

扩展阅读

视频课程

有效学习:明确的目标 及时的反馈 拉伸区(难度合适),可以先学简单的课程,请移步CSDN学院,听白银讲师(也就是鄙人)的讲解。
https://edu.csdn.net/course/detail/38771

如何你想快

速形成战斗了,为老板分忧,请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176

相关

下载

想高屋建瓴的学习算法,请下载《喜缺全书算法册》doc版
https://download.csdn.net/download/he_zhidan/88348653

我想对大家说的话
闻缺陷则喜是一个美好的愿望,早发现问题,早修改问题,给老板节约钱。
子墨子言之:事无终始,无务多业。也就是我们常说的专业的人做专业的事。
如果程序是一条龙,那算法就是他的是睛

测试环境

操作系统:win7 开发环境: VS2019 C++17
或者 操作系统:win10 开发环境: VS2022 C++17
如无特殊说明,本算法C++ 实现。

相关文章:

  • 【C++练级之路】【Lv.5】动态内存管理(都2023年了,不会有人还不知道new吧?)
  • Ubuntu22.04-安装后Terminal无法调出
  • 【Linux学习笔记】Linux下nginx环境搭建
  • Mybatis-Plus基础之Mapper的映射规则
  • 【WPF】使用Behavior以及ValidationRule实现表单校验
  • 亚马逊云科技 re:Invent 大会 - ElastiCache Serverless 模式来袭
  • 线性代数基础【3】向量
  • Datawhale聪明办法学Python(竞赛题解版)
  • HBase基础知识(七):HBase 性能优化示例全解
  • isp代理/双isp代理/数据中心代理的区别?如何选择?
  • 智能三维数据虚拟现实电子沙盘
  • 图片素材管理软件Eagle for mac提高素材整理维度
  • 详解Keras3.0 Layer API: LSTM layer
  • 直接插入排序和希尔排序
  • GPT在企业自动化方面的应用
  • ES6, React, Redux, Webpack写的一个爬 GitHub 的网页
  • gitlab-ci配置详解(一)
  • java取消线程实例
  • JS笔记四:作用域、变量(函数)提升
  • LintCode 31. partitionArray 数组划分
  • 第2章 网络文档
  • 给自己的博客网站加上酷炫的初音未来音乐游戏?
  • 基于webpack 的 vue 多页架构
  • 看域名解析域名安全对SEO的影响
  • 猫头鹰的深夜翻译:Java 2D Graphics, 简单的仿射变换
  • 你不可错过的前端面试题(一)
  • 排序算法之--选择排序
  • 前言-如何学习区块链
  • 如何使用 JavaScript 解析 URL
  • 一个项目push到多个远程Git仓库
  • 一起参Ember.js讨论、问答社区。
  • 用 vue 组件自定义 v-model, 实现一个 Tab 组件。
  • AI又要和人类“对打”,Deepmind宣布《星战Ⅱ》即将开始 ...
  • 摩拜创始人胡玮炜也彻底离开了,共享单车行业还有未来吗? ...
  • ​MPV,汽车产品里一个特殊品类的进化过程
  • ###51单片机学习(1)-----单片机烧录软件的使用,以及如何建立一个工程项目
  • $.each()与$(selector).each()
  • (2)Java 简介
  • (delphi11最新学习资料) Object Pascal 学习笔记---第14章泛型第2节(泛型类的类构造函数)
  • (超简单)构建高可用网络应用:使用Nginx进行负载均衡与健康检查
  • (二)hibernate配置管理
  • (二十五)admin-boot项目之集成消息队列Rabbitmq
  • (附源码)spring boot基于Java的电影院售票与管理系统毕业设计 011449
  • (机器学习-深度学习快速入门)第三章机器学习-第二节:机器学习模型之线性回归
  • ****** 二十三 ******、软设笔记【数据库】-数据操作-常用关系操作、关系运算
  • .net 7 上传文件踩坑
  • .NET 8 中引入新的 IHostedLifecycleService 接口 实现定时任务
  • .Net MVC + EF搭建学生管理系统
  • .NET开源快速、强大、免费的电子表格组件
  • /usr/bin/env: node: No such file or directory
  • @KafkaListener注解详解(一)| 常用参数详解
  • [2010-8-30]
  • [2018][note]用于超快偏振开关和动态光束分裂的all-optical有源THz超表——
  • [android] 天气app布局练习
  • [Android]如何调试Native memory crash issue