59-I. 滑动窗口的最大值
1. 描述
给定一个数组 nums 和滑动窗口的大小 k，请找出所有滑动窗口里的最大值。
2. 例子
示例 1:
输入: nums = [1,3,-1,-3,5,3,6,7], 和 k = 3
输出: [3,3,5,5,6,7]
解释:
滑动窗口的位置 最大值
[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
3. 提示
- 你可以假设 k 总是有效的，在输入数组不为空的情况下，1 ≤ k ≤ 输入数组的大小。
4. 题解
n = i_nums.size()
时间复杂度: O(n)
空间复杂度: O(k)
利用一个双端队列来保存可能的当前窗口最大值，队列的首部是最大值
每处理一个新的值时，我们从后边向前检查是否有比其小的值，因为我们求的是最大值，当前值可以成为最大值时比它小的值都不再有意义。持续该过程，直到队列为空或者遇到了比其更大的值。
同时，为了保持窗口大小，我们需要检查队列首部是不是要退出窗口的值，以便将其从队列中删除。这也就是为什么我们需要双端队列，我们需要从两边 pop 值
同时可以看出，队列最大容量是滑动窗口大小。当数组递增时，每次都会增值新的值，同时减去要离开窗口的值，所以可以将队列大小维持在窗口大小
class Solution
{
public:
// vector<int> maxSlidingWindow(vector<int>& nums, int k)
vector<int> maxSlidingWindow(vector<int> &i_nums, int k)
{
deque<int> possibleMaxValues;
vector<int> maxValues;
for(int i = 0; i < i_nums.size(); i++)
{
while(!possibleMaxValues.empty() && i_nums[i] > possibleMaxValues.back())
possibleMaxValues.pop_back();
possibleMaxValues.push_back(i_nums[i]);
if(i + 1 >= k)
{
maxValues.push_back(possibleMaxValues.front());
if(possibleMaxValues.front() == i_nums[i + 1 - k])
possibleMaxValues.pop_front();
}
}
return maxValues;
}
};