温州市职业中专学校南通百度seo代理

链接：

剑指 Offer 59 - I. 滑动窗口的最大值

题意：

一个lg长度的数组，一个长度k的滑动窗口，求所有滑动窗口中的最大值

解：

优先队列存储存储下标，数字大的优先，每次判断最大的值是否在范围内即可

进阶思想：双端队列

思想核心：当l<r 且 nums[l]<nums[r]的情况下使用nums[r]替换nums[l]

队列存储下标，由于正序遍历，每次加入双端队列的数字一定大于队列内的数，假设我们用front端存储目前最大数字的下标，那么应该从back端开始比较，移除所有nums[old]<nums[now]，再加入自身now。

剩下的数值从front到back依照nums[f]>nums[b] 且 f<b，这时候判断front的下标是否符合范围即可

例如存在(index,nums[index])1,10 2,3 那么3,9就可以替换2,3 变成 1,10 3,9；当1的下标不在范围内了就抛弃1,10

实际代码：

#include<bits/stdc++.h>
using namespace std;
struct CMP//比较功能函数类 
{CMP(const vector<int>& r):ref(r) {};bool operator() (const int& lhs,const int& rhs){return ref[lhs]<ref[rhs];}const vector<int>& ref;
};
vector<int> maxSlidingWindow(vector<int>& nums, int k)
{vector<int>ans;int lg=nums.size();if(!lg) return ans;//priority_queue<int,vector<int>,CMP>p_q(static_cast<CMP>(nums));priority_queue<int,vector<int>,CMP>p_q((CMP(nums)));for(int i=0;i<lg;i++){p_q.push(i);if(i>=k-1) {while(p_q.top()<(i-k+1))p_q.pop();ans.push_back(nums[p_q.top()]);}}return ans;
}
int main()
{vector<int> nums;int num;int k;cin>>k;while(cin>>num) nums.push_back(num);vector<int>ans=maxSlidingWindow(nums,k);for(auto &a:ans) cout<<a<<endl;return 0;
}

进阶：

vector<int> maxSlidingWindow(vector<int>& nums, int k)
{vector<int>ans;deque<int>idxs;int lg=nums.size();if(!lg) return ans;for(int i=0;i<lg;i++){while(!idxs.empty() && nums[i]>nums[idxs.back()])idxs.pop_back();idxs.push_back(i);if(i>=k-1){while(!idxs.empty() && idxs.front()<i-k+1) idxs.pop_front();ans.push_back(nums[idxs.front()]);}}return ans;
}

限制：

• 你可以假设 k 总是有效的，在输入数组 不为空 的情况下，1 ≤ k ≤ nums.length