[LeetCode] 239. Sliding Window Maximum
题目
You are given an array of integers nums, there is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves right by one position.
Return the max sliding window.
Example 1:
Input: nums = [1,3,-1,-3,5,3,6,7], k = 3
Output: [3,3,5,5,6,7]
Explanation:
Window position Max
--------------- -----
[1 3 -1] -3 5 3 6 7 3
1 [3 -1 -3] 5 3 6 7 3
1 3 [-1 -3 5] 3 6 7 5
1 3 -1 [-3 5 3] 6 7 5
1 3 -1 -3 [5 3 6] 7 6
1 3 -1 -3 5 [3 6 7] 7
思路
对于在同一个窗口的元素 x[i], x[j](x < j)：
-
若 x[i] < x[j], 则 x[i] 不可能为当前窗口的最大值，同样也不可能是后面窗口的最大值，故 x[i] 可以丢掉。
-
若 x[j] < x[i], x[j] 可能是后面窗口的最大值（因为 j 位置靠后）。
这样就可以维护一个单调递减的队列。
代码
class Solution {
public:
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
int n = nums.size();
vector<int> ans;
int head = 0, tail = -1;
int q[n + 1];
for (int i = 0; i < n; i++) {
while (tail >= head && i - q[head] + 1 > k) head++;
while (tail >= head && nums[q[tail]] <= nums[i]) tail--;
q[++tail] = i;
if (i >= k-1) ans.push_back(nums[q[head]]);
}
return ans;
}
};