南昌集团制作网站开发,学校让做网站做完怎么交,wordpress 最近登录地址,网站构建设计思路目录
一#xff0c;单调队列
二#xff0c;模板实现
三#xff0c;OJ实战
剑指 Offer 59 - I. 滑动窗口的最大值 一#xff0c;单调队列
单调队列是双端队列的拓展#xff0c;支持尾部插入#xff0c;双端删除#xff0c;其中的数据始终维持单调性#xff0c;从而…目录
一单调队列
二模板实现
三OJ实战
剑指 Offer 59 - I. 滑动窗口的最大值 一单调队列
单调队列是双端队列的拓展支持尾部插入双端删除其中的数据始终维持单调性从而队首就是所需的最值信息。
和单调栈类似单调队列用于处理一个数组扫描数组时依次尾部插入一个数。
尾部插入过程中为了维持单调性可能需要先执行尾部删除对应强制单调栈。
而队首的删除操作由外部决定调用时机。 二模板实现 //单调队列
class MonotonicQueue {
public:MonotonicQueue(int type) { //0递增队列队首最小1递减队列队首最大this-type type;id 0;}void push_back(int x) {while (!q.empty() (type ? (m[q.back()] x) : (m[q.back()] x)))q.pop_back();q.push_back(id);m[id] x;}void pop_front() {if (!q.empty())q.pop_front();}void pop_back() {if (!q.empty())q.pop_back();}int frontId() {return q.front();}int front() {return m[q.front()];}int tailId() {return q.back();}int size() {return q.size();}
private:dequeintq;mapint, intm;int type, id;
};
三OJ实战
剑指 Offer 59 - I. 滑动窗口的最大值
题目
给定一个数组 nums有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
返回滑动窗口中的最大值。
进阶
你能在线性时间复杂度内解决此题吗
示例:
输入: 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
提示
1 nums.length 10^5 -10^4 nums[i] 10^4 1 k nums.length 思路一
线段树
class SegmentTree2 opt;class Solution {
public:vectorint maxSlidingWindow(vectorint nums, int k) {int n nums.size();for (int i 0; i n; i)*(opt.getData() i 1) nums[i];opt.build(n);vectorintans;ans.resize(n - k 1);for (int i 0; i ans.size(); i)ans[i] opt.query(i 1, i k);return ans;}
};
思路二
单调队列
class Solution {
public:vectorint maxSlidingWindow(vectorint nums, int k) {vectorintans;MonotonicQueue q(1);for (int i 0; i k; i)q.push_back(nums[i]);for (int i k; i nums.size(); i) {ans.push_back(q.front());q.push_back(nums[i]);if (q.tailId() - k q.frontId())q.pop_front();}ans.push_back(q.front());return ans;}
};
