原题链接
题意：
给定一个数组数字，有一个大小为k的滑动窗口，它从数组的最左边移动到最右边。你只能在窗口看到k个数字。每次滑动窗口向右移动一个位置。
记录每一次窗口内的最大值，返回记录的值。
思路：
解法一：
一开始用的c++迭代器来模拟窗口，每移动一次就遍历一次找出最大值填入返回数组中。
效率非常低 Runtime: 108 ms, faster than 7.98% of C++
class Solution { public: vector<int> maxSlidingWindow(vector<int> &nums, int k) { int len = nums.size(); vector<int> vec; if (len == 0) return vec; vector<int>::iterator iter = nums.begin(); for (int i = 0; i + k <= len; i++) { vec.push_back(*max_element(iter + i, iter + i + k)); } return vec; } };解法二：
在Discuss中看到大家普遍用的一直优解思路：
用一个双端队列deque保存每一个窗口里的最大值的索引，同时该队列保存的索引为有序的。
Runtime: 60 ms, faster than 45.44% of C++
class Solution { public: vector<int> maxSlidingWindow(vector<int> &nums, int k) { deque<int> dq; vector<int> ans; for (int i = 0; i < nums.size(); i++) { if (!dq.empty() && dq.front() == i - k) dq.pop_front(); while (!dq.empty() && nums[dq.back()] < nums[i]) dq.pop_back(); dq.push_back(i); if (i >= k - 1) ans.push_back(nums[dq.front()]); } return ans; } };
转载于:https://www.cnblogs.com/ruoh3kou/p/9917162.html
