搜索

前言

看到滑动窗口以及示例,很容易被思维局限了,然后呢就开始打框架,用一个for循环,i-i+3这样的范围一直移动,但是每次都要比较这3个值的大小,如何比较呢?用类似之前T155的栈一样比较吧。但是存在一个问题,有些值就重复2-3次,似乎没有这个必要。

因此,这里我理解了别人的方法,灭掉了自己危险的想法。

解决方案

不使用一个i了,把它看成一个区间[i,j],也不要k个k个这样块移动着看。每次移动,i+1,j+1。而比较采用类似T155却是双端队列的结构,全部一起来比较,这样每个只会比较1次了。

首先来定i和j的范围,i是开头,j是结尾,我们定每次的j为索引,给队列添加值,因此i就要往前移,去1-k的位置。

左边界范围 i ∈ [1 - k, n - k]右边界范围 j ∈ [0, n - 1]

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        deque<int> d;
        vector<int> maxNums;
        auto n = nums.size();
        for(int i= 1- k,j=0;j<n;i++,j++){
            if (i > 0 && d.front() == nums[i-1]){
                d.pop_front();
            }
            while(!d.empty()&&d.back()<nums[j]){
                d.pop_back();
            }
            d.push_back(nums[j]);
            if(i>=0){
                maxNums.push_back(d.front());
            }
        }
        return maxNums;
    }
};

c++ STL为我们直接提供了双端队列,我们直接引用。

每次去比较队列最后的值是否比要入列的值小,如果是那就删去,保留比它大的。最大的值永远是队首。

当i=0的时候,这个窗口才开始形成了。这时候才可以开始每次移动把队首的值加入数组,组成最大值数组

我们在i+1的时候,可能队首的值在移动中被删除了,(是上一个窗口的)那么队列也要做出改变删除,不然无法开始新窗口的比较。

附录双端队列的一些方法

方法介绍
pop_front删除第一个元素
front获取第一个元素
back获取最后一个元素
pop_back删除最后一个元素
push_back向最后添加元素

版权属于:染念
作品采用:本作品采用 知识共享署名-相同方式共享 4.0 国际许可协议 进行许可。
11
查看目录

目录

来自 《LeetCode239|剑指 Offer 59 - I. 滑动窗口的最大值》
评论

  1. 评论头像
    2021-08-01 回复

    感谢博主的分享,支持了。
    技术文章,学习了。

博主很懒,啥都没有