设计素材网站花瓣,免费下载微信2023,个人网站页面设计素材,深圳网站建设是什么前言 题目#xff1a; 239. 滑动窗口最大值 文档#xff1a; 代码随想录——滑动窗口最大值 编程语言#xff1a; C 解题状态#xff1a; 没有思路#xff0c;困难题#xff0c;恐怖如斯 思路
本题的关键在于对单调队列的应用#xff0c;时间复杂度 O ( n ) O(n) O(n)限…前言 题目 239. 滑动窗口最大值 文档 代码随想录——滑动窗口最大值 编程语言 C 解题状态 没有思路困难题恐怖如斯 思路
本题的关键在于对单调队列的应用时间复杂度 O ( n ) O(n) O(n)限制了本题的做法。
代码
class Solution {
private:class MyQueue {public:dequeint que;// 每次弹出之前要比较弹出的数值是否等于队列出口元素的数值如果相等则弹出void pop(int value) {if (!que.empty() value que.front()) {que.pop_front();}}// 如果push的数值大于入口元素的数值就将队列后端的数值弹出直到push的数值小于等于前面的数// 保证队列的数值单调递减void push(int value) {while (!que.empty() value que.back()) {que.pop_back();}que.push_back(value);}// 查询最大值直接返回队列前端就可以int front() {return que.front();}};
public:vectorint maxSlidingWindow(vectorint nums, int k) {MyQueue que;vectorint 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)空间复杂度 O ( k ) O(k) O(k)
