滑动窗口最大值
时间: 2023-07-19 17:12:59 浏览: 36
滑动窗口最大值问题是指给定一个长度为 n 的整型数组 nums 和一个正整数 k,从数组的最左边开始,滑动一个长度为 k 的窗口,每次向右移动一个位置,求出每个窗口中元素的最大值。
解决这个问题可以使用双端队列(deque)来维护每个窗口的最大值。具体思路是:双端队列中存储的是当前窗口中的元素下标,队头元素为当前窗口中的最大值。每次向右移动窗口时,将队头元素所对应的值加入结果数组中,并将队头元素弹出。然后将新元素从队尾依次与队列中的元素比较,如果比队列中的元素大,则将队列中的元素弹出,直到队列为空或者队列中的元素比新元素大为止。最后将新元素的下标加入队尾。这样就可以维护一个单调递减的队列,队列中的元素是当前窗口中的最大值及其后续的可能成为最大值的元素。
以下是C++实现代码:
```cpp
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
vector<int> res;
deque<int> q;
for (int i = 0; i < nums.size(); i++) {
if (!q.empty() && q.front() == i - k) q.pop_front(); // 弹出队头元素
while (!q.empty() && nums[q.back()] < nums[i]) q.pop_back(); // 从队尾依次弹出比新元素小的元素
q.push_back(i); // 将新元素加入队尾
if (i >= k - 1) res.push_back(nums[q.front()]); // 将队头元素加入结果数组
}
return res;
}
```