【算法与数据结构】239、LeetCode滑动窗口最大值

news/2024/10/30 17:23:09/

文章目录

  • 一、题目
  • 二、解法
  • 三、完整代码

所有的LeetCode题解索引,可以看这篇文章——【算法和数据结构】LeetCode题解。

一、题目

在这里插入图片描述

二、解法

  思路分析:这道题我们如果用暴力破解法需要 O ( n ∗ k ) O(n*k) O(nk)的复杂度。思索再三,我们需要一个能够把最大值放在队头,整个队列单调递减的单调队列。每次窗口移动的时候,调用que.pop(滑动窗口中移除元素的数值),que.push(滑动窗口添加元素的数值),然后que.front()就返回我们要的最大值。要注意两点:1、最大值必须在队头,这样我们才能用que.front()访问 2、队头的最大值元素必须在滑动窗口内部,否则就不是滑动窗口的最大值

  对于上面两个问题我们分别在pop和push中做这样的逻辑:1、如果队尾元素如果小于入队元素,就弹出队尾元素,直到入队元素大于等于队尾元素才插入入队元素 2、每次访问que.front()之前,都进行一次判断,如果队头的最大值和nums[i-k]进行对比,如果相等,说明这个最大值元素不在滑动窗口中(滑动窗口范围为i-k+1,…,i-1,i)
  程序如下

class MyQueue {	// 单调队列,递减
public:deque<int> que;		// deque为双向数组,这里用它当做单调队列的底层实现void pop(int value) {	if (!que.empty() && value == que.front())	// 如果元素相等则弹出,否则不做操作que.pop_front();}void push(int value) {	// 保证队头元素一定是最大的while (!que.empty() && value > que.back()) {	// 队尾元素如果小于入队元素,就弹出队尾元素que.pop_back();}que.push_back(value);	// 直到入队元素大于等于队尾元素,插入}int front() {return que.front();}
};class Solution {
public:vector<int> maxSlidingWindow(vector<int>& nums, int k) {MyQueue que;	// 单调队列vector<int> result;for (int i = 0; i < k; ++i) {que.push(nums[i]);}result.push_back(que.front());for (int i = k; i < nums.size(); ++i) {que.pop(nums[i - k]);	// 弹出队头的元素,防止最大值一直在队头,且这个最大值又不在滑动窗口中的情况que.push(nums[i]);result.push_back(que.front());}return result;}
};

复杂度分析:

  • 时间复杂度: O ( n ) O(n) O(n),所有元素的push和pop操作都只进行一次。
  • 空间复杂度: O ( k ) O(k) O(k),需要一个大小为k的单调队列额外空间。

三、完整代码

# include <iostream>
# include <vector>
# include <deque>
using namespace std;class MyQueue {	// 单调队列,递减
public:deque<int> que;		// deque为双向数组,这里用它当做单调队列的底层实现void pop(int value) {	if (!que.empty() && value == que.front())	// 如果元素相等则弹出,否则不做操作que.pop_front();}void push(int value) {	// 保证队头元素一定是最大的while (!que.empty() && value > que.back()) {	// 队尾元素如果小于入队元素,就弹出队尾元素que.pop_back();}que.push_back(value);	// 直到入队元素大于等于队尾元素,插入}int front() {return que.front();}
};class Solution {
public:vector<int> maxSlidingWindow(vector<int>& nums, int k) {MyQueue que;	// 单调队列vector<int> result;for (int i = 0; i < k; ++i) {que.push(nums[i]);}result.push_back(que.front());for (int i = k; i < nums.size(); ++i) {que.pop(nums[i - k]);	// 弹出队头的元素,防止最大值一直在队头,且这个最大值又不在滑动窗口中的情况que.push(nums[i]);result.push_back(que.front());}return result;}
};void my_print(vector <int>& v, string msg)
{cout << msg << endl;for (vector<int>::iterator it = v.begin(); it != v.end(); it++) {cout << *it << "  ";}cout << endl;
}void VectorGenerator(int* arr, vector<int>& v, int arr_len) {for (int i = 0; i < arr_len; ++i) {v.push_back(arr[i]);}
}int main()
{int window_size = 3;int arr[] = {1, 3, -1, -3, 5, 3, 6, 7};int arr_len = sizeof(arr) / sizeof(int);vector<int> nums;VectorGenerator(arr, nums, arr_len);my_print(nums, "目标数组");Solution s1;vector<int> result = s1.maxSlidingWindow(nums, window_size);my_print(result, "滑动窗口最大值");system("pause");return 0;
}

end


http://www.ppmy.cn/news/836519.html

相关文章

create-react-app中配置支持less

这玩意确实挺好 但如果想开发一个完整的项目 很多配置都得自己来搞 相当于从零开始了 直接比较复杂的项目 还是基于umi进行开发吧 比如项目中我想配置使用less 都得让我自己去搞着配置webpack 有的博客可能让你直接运行 npm run eject让后暴露出来webpack的配置文件 然后在里…

【算法专题】多项式运算与生成函数

【快速傅里叶变换】FFT 参考&#xff1a;从多项式乘法到快速傅里叶变换 by miskcoo FFT 学习笔记 by Menci &#xff08;一&#xff09;多项式的表示法 系数表示法&#xff1a;f(x)a[n-1]*x^(n-1)...a[0]&#xff0c;称为n-1次多项式。 点值表示法&#xff1a;一个n-1次多项式在…

selenium 总结篇,常见方法和页面元素的操作

selenium 总结篇&#xff0c;常见方法和页面元素的操作 今天&#xff0c;总结一下selenium怎么操作web页面常见的元素。 主要有&#xff1a; 上传alter dialogprompt dialogconfirm dialogselect listradio boxinput boxcheckBox 测试页面如下&#xff1a; View Code selenium …

清北学堂培训2019.4.28

Day 1&#xff08;冯哲&#xff09; 今天的内容很杂但却都是基础知识 主要分为下面几个点 枚举 枚举也称作穷举&#xff0c;指的是从问题所有可能的解的集合中一一枚举各元素。用题目中给定的检验条件判定哪些是无用的&#xff0c;哪些是有用的。能使命题成立的即为其解。 有几…

0x35.数论 - 组合数学与计数

目录 一、计数原理1.加法原理2.乘法原理3.减法原理 二、排列组合1.排列数2.组合数3.数学题 三、组合数的计算1. 加法递推 O ( n 2 ) O(n^2) O(n2)2. 乘法递推 O ( n ) O(n) O(n)3. Lucas定理4. 扩展卢卡斯5. 大组合数&#xff08;高精&#xff09;6. 生成全排列7.枚举子集 四 、…

五一清北学堂培训之数据结构(Day 1Day 2)

Day 1 前置知识&#xff1a; 二进制 2.基本语法 3.时间复杂度 正片 1.枚举 洛谷P1046陶陶摘苹果 入门题没什么好说的 判断素数&#xff1a;从2枚举到sqrt(n),若出现n的因子&#xff0c;则n是合数 因为数据范围比较小&#xff0c;所以直接欧拉筛&#xff0c;再判定在l~r区间内…

Java基础1

目录 1.数据类型分类1.1 基本数据类型【今天重点】1.2 引用数据类型&#xff08;今后学习&#xff09;1.3 注意事项 2. 数据类型转换2.1 自动数据类型转换(隐式)2.2 强制数据类型转换(显式)2.3 字母和汉字的转换 3. 运算符3.1 四则运算符3.2 四则运算中的 (加号)3.3 自增加.减少…

常用代码笔记-持续更新

一&#xff0c;蛇型排n格图精灵 //LatticeImage -(void)LatticeImage:(NSArray *)imageArray_ firstImagePoint:(CGPoint) firstImagePoint_ ColumnStep:(float)ColumnStep_ LineStep:(float)linestep_{for(int i0; i<imageArray_.count;i) {NSString* image[imageArray_ ob…