12306网站开发商,金华网站制作企业,wordpress 密码 hello,建信网个人证书查询链接#xff1a;
剑指 Offer 59 - I. 滑动窗口的最大值
题意#xff1a;
一个lg长度的数组#xff0c;一个长度k的滑动窗口#xff0c;求所有滑动窗口中的最大值
解#xff1a;
优先队列存储存储下标#xff0c;数字大的优先#xff0c;每次判断最大的值是否在范围…链接
剑指 Offer 59 - I. 滑动窗口的最大值
题意
一个lg长度的数组一个长度k的滑动窗口求所有滑动窗口中的最大值
解
优先队列存储存储下标数字大的优先每次判断最大的值是否在范围内即可
进阶思想双端队列
思想核心当lr 且 nums[l]nums[r]的情况下使用nums[r]替换nums[l]
队列存储下标由于正序遍历每次加入双端队列的数字一定大于队列内的数假设我们用front端存储目前最大数字的下标那么应该从back端开始比较移除所有nums[old]nums[now]再加入自身now。
剩下的数值从front到back依照nums[f]nums[b] 且 fb这时候判断front的下标是否符合范围即可
例如存在(index,nums[index])1,10 2,3 那么3,9就可以替换2,3 变成 1,10 3,9当1的下标不在范围内了就抛弃1,10
实际代码
#includebits/stdc.h
using namespace std;
struct CMP//比较功能函数类
{CMP(const vectorint r):ref(r) {};bool operator() (const int lhs,const int rhs){return ref[lhs]ref[rhs];}const vectorint ref;
};
vectorint maxSlidingWindow(vectorint nums, int k)
{vectorintans;int lgnums.size();if(!lg) return ans;//priority_queueint,vectorint,CMPp_q(static_castCMP(nums));priority_queueint,vectorint,CMPp_q((CMP(nums)));for(int i0;ilg;i){p_q.push(i);if(ik-1) {while(p_q.top()(i-k1))p_q.pop();ans.push_back(nums[p_q.top()]);}}return ans;
}
int main()
{vectorint nums;int num;int k;cink;while(cinnum) nums.push_back(num);vectorintansmaxSlidingWindow(nums,k);for(auto a:ans) coutaendl;return 0;
}进阶
vectorint maxSlidingWindow(vectorint nums, int k)
{vectorintans;dequeintidxs;int lgnums.size();if(!lg) return ans;for(int i0;ilg;i){while(!idxs.empty() nums[i]nums[idxs.back()])idxs.pop_back();idxs.push_back(i);if(ik-1){while(!idxs.empty() idxs.front()i-k1) idxs.pop_front();ans.push_back(nums[idxs.front()]);}}return ans;
}限制
你可以假设 k 总是有效的在输入数组 不为空 的情况下1 ≤ k ≤ nums.length
