宁波网站优化体验,广告公司名称大全简单,wordpress能大网站,wordpress禁止留言滑动窗口的最大值
题目描述
给定一个数组和滑动窗口的大小#xff0c;请找出所有滑动窗口里的最大值。
例如#xff0c;如果输入数组 [2,3,4,2,6,2,5,1] 及滑动窗口的大小 3 #xff0c;那么一共存在 6 个滑动窗口#xff0c;它们的最大值分别为 [4,4,6,6,6,5]
注意请找出所有滑动窗口里的最大值。
例如如果输入数组 [2,3,4,2,6,2,5,1] 及滑动窗口的大小 3 那么一共存在 6 个滑动窗口它们的最大值分别为 [4,4,6,6,6,5]
注意 数据保证 k大于 0且 k小于等于数组长度。 数据范围 数组长度 [1,1000]
样例 输入[2, 3, 4, 2, 6, 2, 5, 1] , k3 输出: [4, 4, 6, 6, 6, 5]
思路
模拟窗口的滑动 当窗口里有k个元素的时候 向后滑动
检查窗口内元素是否合法窗口的一端纳入一个元素窗口的另一端移除一个元素
由于符合先进先出的原则所以可以用队列来模拟窗口 然后进一步挖掘性质
假设公司里有一群员工 现在来了一个新员工A 如果员工A的能力出众 并且年纪小 那么
A可以替换掉所有员工中能力小于等于A的员工A可以替换掉所有员工中年龄小于等于A的员工
能力-本题的数值 年龄-本题的索引
那么
为什么上面的性质合理呢 因为滑动窗口需要的是最大值所以只要当前元素大于队列中元素那么队列中元素就不需要了为什么可以取等 因为两个数值一样的元素并列 例如int a[3] {1, 1, 1};, a数组里三个元素均相等那么当需要最大值的时候 取a[2]一定没错 因为如果返回a[0] 那么窗口移动以后a[0]会被移除a[1]同理
也就是说a[2]活到了最后
所以 最终队列会形成一个递减序列 因此 队头元素就是最大值 每次从队头里获取最大值放入到结果数组中
代码
class Solution {
public:vectorint maxInWindows(vectorint nums, int k) {vectorint res;dequeint q;for (int i 0; i nums.size(); i ){if (q.size() i - q.front() k) q.pop_front();while (q.size() nums[q.back()] nums[i]) q.pop_back();q.push_back(i);if (i k - 1) res.push_back(nums[q.front()]);}return res;}
};
