剑指offer题解合集——Week7day1[滑动窗口的最大值]

滑动窗口的最大值

题目描述

给定一个数组和滑动窗口的大小，请找出所有滑动窗口里的最大值。

例如，如果输入数组 [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] , k=3
输出: [4, 4, 6, 6, 6, 5]

思路

模拟窗口的滑动
当窗口里有k个元素的时候， 向后滑动

• 检查窗口内元素是否合法
• 窗口的一端纳入一个元素
• 窗口的另一端移除一个元素

由于符合先进先出的原则，所以可以用队列来模拟窗口
然后进一步挖掘性质：

假设公司里有一群员工， 现在来了一个新员工A， 如果员工A的能力出众， 并且年纪小， 那么

1. A可以替换掉所有员工中能力小于等于A的员工
2. A可以替换掉所有员工中年龄小于等于A的员工

能力->本题的数值
年龄->本题的索引

那么：

1. 为什么上面的性质合理呢？
   因为滑动窗口需要的是最大值，所以，只要当前元素大于队列中元素，那么队列中元素就不需要了
2. 为什么可以取等？
   因为两个数值一样的元素并列， 例如int a[3] = {1, 1, 1};, a数组里三个元素均相等，那么当需要最大值的时候
   取a[2]一定没错， 因为如果返回a[0]， 那么窗口移动以后，a[0]会被移除，a[1]同理

也就是说，a[2]活到了最后

所以：
最终队列会形成一个递减序列， 因此， 队头元素就是最大值
每次从队头里获取最大值，放入到结果数组中

代码

class Solution {
public:vector<int> maxInWindows(vector<int>& nums, int k) {vector<int> res;deque<int> 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;}
};