双端单调队列 滑动窗口
时间: 2023-08-31 08:12:19 浏览: 55
双端单调队列是一种数据结构,可以在O(1)时间复杂度内进行队列的插入、删除等操作,同时还可以维护队列中元素的单调性。在滑动窗口问题中,可以使用双端单调队列来维护窗口中的最大值或最小值,从而在O(n)时间复杂度内解决问题。具体操作是,在队列中保存元素的下标,队列中的元素满足单调性,即队头元素为当前窗口中的最大值或最小值。每次向右移动窗口时,先将窗口右端的元素加入队列中,然后判断队列中队头元素是否已经不在窗口内,不在窗口内则弹出队头元素,直到队头元素在窗口内为止。这样,队列中的队头元素就是当前窗口中的最大值或最小值了。
相关问题
单调队列滑动窗口c++
单调队列(Monotonic Queue)是一种数据结构,它可以用来解决一类滑动窗口问题。滑动窗口问题是指在一个长度为n的数组中,长度为k的窗口从左往右移动,每次移动一位,求出每个窗口的最大值或最小值。
单调队列的思想就是维护一个单调递增或递减的队列,队列中的元素从队头到队尾是单调递增或递减的。当窗口向右移动时,先将队头元素出队,然后将新的元素从队尾入队,保持队列的单调性。这样就可以实现每个窗口的最大值或最小值的求解。
下面是单调队列求解滑动窗口最大值的C++代码:
```c++
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
vector<int> res;
deque<int> dq;
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) {
res.push_back(nums[dq.front()]);
}
}
return res;
}
```
在上述代码中,使用双端队列deque来实现单调队列。dq.front()表示队头元素的下标,dq.back()表示队尾元素的下标。当队列为空时,dq.front()和dq.back()都是未定义的。
时间复杂度:O(n),每个元素最多被插入和删除一次。
空间复杂度:O(k),队列中最多存储k个元素。
双端队列滑动窗口最大值C++
为了求解双端队列滑动窗口的最大值C,需要使用一个双端队列来维护滑动窗口中的元素。在遍历整个序列时,我们不断地将元素添加到队列的尾部,并检查队列头部的元素是否已经超出了滑动窗口的范围,如果是,则将其从队列头部删除。同时,我们需要维护一个队列中元素的单调性,即队列中的元素应该按照从大到小的顺序排列。这样,队列头部的元素就是当前滑动窗口中的最大值。因此,当一个新的元素要进入队列时,我们需要将队列尾部所有比它小的元素都弹出,并将其自身插入到队列尾部。这样,我们就能在O(n)的时间内求出滑动窗口的最大值序列C了。