剑指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;
    }
};

原文地址：https://blog.csdn.net/qq_51931826/article/details/140859370

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！