首页 书籍 深入浅出程序设计竞赛(进阶篇) 常见优化技巧

单调队列是一种特殊的队列结构，用于解决滑动窗口类问题，尤其是那些涉及到在滑动窗口内寻找最大值或最小值的问题。与单调栈类似，单调队列内部的元素也保持一个单调递增或单调递减的顺序。通过维护这种单调性，单调队列能够在 O (1) 时间复杂度内给出窗口内的最大值或最小值，从而使得整个问题的时间复杂度降低。

# 工作原理

  • 单调递增队列：用于解决滑动窗口中寻找窗口最小值的问题。当新元素加入队列时，从队列尾部开始，移除所有小于新元素的旧元素，以保持队列的单调递增性。

  • 单调递减队列：用于解决滑动窗口中寻找窗口最大值的问题。当新元素加入队列时，从队列尾部开始，移除所有大于新元素的旧元素，以保持队列的单调递减性。

# 示例：

滑动窗口最大值

下面是使用单调队列解决滑动窗口最大值问题的 C++ 示例代码：

#include <iostream>
#include <vector>
#include <deque>
using namespace std;
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
    deque<int> dq; // 存储数组元素索引的单调递减队列
    vector<int> result;
    
    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);
        
        // 当窗口大小达到 k 时，将窗口的最大值加入结果
        if (i >= k - 1) {
            result.push_back(nums[dq.front()]);
        }
    }
    
    return result;
}
int main() {
    vector<int> nums = {1,3,-1,-3,5,3,6,7};
    int k = 3;
    vector<int> result = maxSlidingWindow(nums, k);
    for (int num : result) {
        cout << num << " ";
    }
    cout << endl;
    
    return 0;
}
在这个例子中，我们使用了一个双端队列（ deque<int> ）来实现单调递减队列。队列中存储的是元素的索引，而不是元素的值。这样做的目的是方便我们判断队列头部的元素是否已经超出了当前滑动窗口的范围。当遍历到数组中的一个新元素时，我们首先检查队列头部的元素是否超出了窗口范围，如果是，则从队列头部移除。然后，从队列尾部开始，移除所有小于当前元素值的元素索引，以保持队列的单调递减性。之后，将当前元素的索引加入队列尾部。当窗口大小达到 k 时，队列头部的元素即为当前窗口的最大值，将其加入结果数组中。


通过这种方式，我们可以在 O (n) 的时间复杂度内解决滑动窗口最大值问题，其中 n 是数组的长度。这种方法比暴力求解的 O (nk) 时间复杂度有显著的改进。


      

          
          
      

  


   


    

  
    
      
    
    更新于