题目描述
滑动窗口的最大值
样例
输入:[2, 3, 4, 2, 6, 2, 5, 1] , k=3
输出: [4, 4, 6, 6, 6, 5]
算法1
(单调队列)
在固定大小窗口内维持一个单调递减的队列,然后在滑动窗口的时候不断地更新队列,队列的首元素就是该窗口的最大值。
我实现的方法是在队列中存储了窗口内的元素,剑指offer存储的是元素的下标,解法相同,但不一样,但是都对,代码是惊人的相似。具体详情看下述代码吧。
时间复杂度
O(n)
参考文献
剑指offer
C++ 代码
vector<int> maxInWindows(vector<int>& nums, int k) {
if(nums.size() == 1)
return nums;
deque<int> help;
vector<int> ans;
int i = 0;
help.push_back(nums[0]);
for(i = 1; i < k; ++i)
{
while(!help.empty() && nums[i] > help.back())
help.pop_back();
help.push_back(nums[i]);
}
ans.push_back(help.front());
int leftIndex = 0;
for(; i < nums.size(); ++i)
{
if(!help.empty() && help.front() == nums[leftIndex++])
help.pop_front();
while(!help.empty() && nums[i] > help.back())
help.pop_back();
help.push_back(nums[i]);
ans.push_back(help.front());
}
return ans;
}