开发中英文切换网站如何做,蚌埠百度推广电话,纵横中文网,长春建设集团网站1 问题描述 2 思路
为了每次元素进出的时候#xff0c;我们都可以得到该窗口内的最大元素#xff0c;我们需要自己定义一种队列里面包含方法可以获取最大值怎么才能获取队列里的最大值呢#xff1f;在队列里排序也可以#xff0c;这里我们采用单调队列#xff1a;该队列…1 问题描述 2 思路
为了每次元素进出的时候我们都可以得到该窗口内的最大元素我们需要自己定义一种队列里面包含方法可以获取最大值怎么才能获取队列里的最大值呢在队列里排序也可以这里我们采用单调队列该队列的队头元素就是该区间的最大值我们只需要维护队头元素就可以
3 代码实现
class MyQueue { //单调队列从大到小
public:dequeint que; // 使用deque来实现单调队列// 每次弹出的时候比较当前要弹出的数值是否等于队列出口元素的数值如果相等则弹出。// 同时pop之前判断队列当前是否为空。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);}// 查询当前队列里的最大值 直接返回队列前端也就是front就可以了。int front() {return que.front();}
};
vectorint maxSlidingWindow(vectorint nums, int k) {int i 0;MyQueue queue;vectorint res;while(i k) {queue.push(nums[i]);// 先将前k的元素放进队列i;}res.push_back(queue.front());// res 记录前k的元素的最大值while(i nums.size()) {queue.pop(nums[i-k]);// 滑动窗口移除最前面元素queue.push(nums[i]);// 滑动窗口添加新元素res.push_back(queue.front());// 记录区间最大值i;}return res;
}3 总结
单调队列解决区间求极值的问题单调队列永远在维护尽可能是最大的值那些肯定不是最大的值在push的过程中就已经被弹出了
