这道题是lintcode上的一道题，当然leetcode上同样有。
本题需要寻找O(N)复杂度的算法。
解体思路比较有特点，所以容易想到参考 最小栈 的解题办法。
但是最小栈用栈维护最小值很直观，这道题是队列，用什么数据结构好呢？也许看完暴力解会有点启发。
但是思路还是一样的，最大的要在最前面（直接获取结果），小的值在后面保留下来（防止之后遍历到的时候丢失数据）。并且某值出窗口的时候需要判断是否要修改排在最前面的值。
一。暴力解
当然直观看，暴力求解是 O(NK)的复杂度，大体的代码如下：（写的有点复杂费劲，主要当时是想通过vector构建头尾可变动的队列，发现STL里其实有就放弃了）
vector<int> maxSlidingWindow(vector<int> &nums, int k) {
// write your code here
if (nums.empty()) return vector<int>();
vector<int> maxVec;
int maxV = INT_MIN;
vector<int> res;
for (int i = ; i < k && i < nums.size(); i++) {
if (maxV < nums[i])
maxV = nums[i];
maxVec.push_back(nums[i]);
}
res.push_back(maxV);
for (int i = k; i < nums.size(); i++) {
maxVec.push_back(nums[i]);
maxVec.erase(maxVec.begin());
if (nums[i - k] == maxV) {
maxV = INT_MIN;
for (int j = ; j < maxVec.size(); j++)
if (maxV < maxVec[j])
maxV = maxVec[j];
}
if (nums[i] > maxV)
maxV = nums[i];
res.push_back(maxV);
}
return res;
}
二。大顶堆
这个其实思路希望通过堆的构造还控制O(1)代价获得最大元素，复杂度O(N * logK)
三。双向队列
终于到它了，其实对自己来说是想提醒自己一下STL里deque的存在。就像priority_queue一样容易被忽略。
思路是维持一个不增序的双向队列，最大值在队首（直接获取结果）。队列大小最多是窗口大小，由值出窗口控制。
最坏case时间复杂度为2N，所以O(N)复杂度。
vector<int> maxSlidingWindow(vector<int> &nums, int k) {
// write your code here
deque<int> my_deq;
vector<int> res;
for (int i = ; i < nums.size(); i++) {
if (i - k >= ) { // 出队列踢头节点判断
if (!my_deq.empty() && nums[i - k] == my_deq.front())
my_deq.pop_front();
}
// 入队列踢值判断
while (!my_deq.empty() && nums[i] > my_deq.back()) my_deq.pop_back();
my_deq.push_back(nums[i]);
if (i + - k >= ) // 窗口大小满足判断
res.push_back(my_deq.front());
}
if (k > nums.size())
res.push_back(my_deq.front());
return res;
}
转载请注明出处~ http://www.cnblogs.com/xiaoboCSer/p/4895191.html