C11第5章单调队列

admin

单调队列的核心原理
单调队列通过 deque 实现，支持在两端进行插入和删除操作，核心是维持队列内元素的单调性（递增或递减）。这种特性使得它能高效解决滑动窗口内的最值问题，时间复杂度从暴力法的 O (nk) 优化到 O (n)。
关键应用场景说明
滑动窗口最大值
核心逻辑：使用单调递减队列存储元素索引，确保队列头部始终是当前窗口的最大值索引。
维护步骤：
移除超出窗口范围的元素（队列头部）；
移除所有小于当前元素的队列尾部元素（它们不可能成为后续窗口的最大值）；
加入当前元素索引；
窗口形成后（i ≥ k-1），记录队列头部对应的元素值。
示例：数组 [1,3,-1,-3,5,3,6,7] 与窗口大小 3，结果为 [3,3,5,5,6,7]。

滑动窗口最小值
核心逻辑：与最大值类似，但使用单调递增队列，确保队列头部是当前窗口的最小值索引。
示例：数组 [4,2,1,3,6,5] 与窗口大小 2，结果为 [2,1,1,3,5]。

最长子数组（最大最小差 ≤ k）
核心逻辑：同时维护两个单调队列（一个存最大值，一个存最小值），通过滑动窗口找到满足条件的最长子数组。
维护步骤：
扩展右边界，更新两个队列；
当最大最小差 > k 时，收缩左边界并更新队列；
记录当前窗口的最大长度。
示例：数组 [8,2,4,7] 与 k=4，结果为 2（子数组 [4,7] 或 [2,4]）。

实际应用价值
单调队列在以下场景中表现突出：
实时数据处理：如监控系统中滑动时间窗口内的峰值数据（CPU 使用率、网络流量）。
金融分析：计算股票价格在连续 N 天内的最高 / 最低价。
字符串匹配：优化滑动窗口模式下的字符频率统计。
其核心优势是用 O (n) 时间解决滑动窗口的最值问题，避免了重复计算，是处理流式数据的高效工具。

[C++] 纯文本查看 复制代码

#include <iostream>
#include <vector>
#include <deque>  // STL双端队列，支持两端插入和删除

using namespace std;

/**
 * 场景1：滑动窗口最大值
 * 给定数组和窗口大小k，返回每个窗口中的最大值
 * 时间复杂度：O(n)，每个元素仅入队和出队一次
 */
vector<int> maxSlidingWindow(const vector<int>& nums, int k) {
    vector<int> result;
    deque<int> q;  // 单调队列，存储元素索引，维持队列内元素值递减
    
    for (int i = 0; i < nums.size(); ++i) {
        // 1. 移除队列中超出当前窗口范围的元素
        // 窗口范围是 [i-k+1, i]，超出左边界的元素需弹出
        if (!q.empty() && q.front() < i - k + 1) {
            q.pop_front();
        }
        
        // 2. 维持队列单调性：移除所有小于当前元素的队列元素
        // 因为这些元素在当前元素右侧，且值更小，不可能成为后续窗口的最大值
        while (!q.empty() && nums[i] >= nums[q.back()]) {
            q.pop_back();
        }
        
        // 3. 将当前元素索引加入队列
        q.push_back(i);
        
        // 4. 当窗口完全形成后（i >= k-1），开始记录结果
        // 队列头部即为当前窗口的最大值索引
        if (i >= k - 1) {
            result.push_back(nums[q.front()]);
        }
    }
    
    return result;
}

/**
 * 场景2：滑动窗口最小值
 * 逻辑与最大值类似，仅需维持队列递增性
 */
vector<int> minSlidingWindow(const vector<int>& nums, int k) {
    vector<int> result;
    deque<int> q;  // 单调队列，存储元素索引，维持队列内元素值递增
    
    for (int i = 0; i < nums.size(); ++i) {
        // 移除超出窗口范围的元素
        if (!q.empty() && q.front() < i - k + 1) {
            q.pop_front();
        }
        
        // 维持队列单调性：移除所有大于当前元素的队列元素
        while (!q.empty() && nums[i] <= nums[q.back()]) {
            q.pop_back();
        }
        
        q.push_back(i);
        
        // 窗口形成后记录结果
        if (i >= k - 1) {
            result.push_back(nums[q.front()]);
        }
    }
    
    return result;
}

/**
 * 场景3：满足条件的子数组的最大长度
 * 给定数组和整数k，找到最长子数组，其最大值与最小值之差 <= k
 * 利用两个单调队列分别维护当前窗口的最大值和最小值
 */
int longestSubarrayWithDiff(const vector<int>& nums, int k) {
    deque<int> maxDeque;  // 维护窗口最大值的单调递减队列
    deque<int> minDeque;  // 维护窗口最小值的单调递增队列
    int left = 0;         // 滑动窗口左边界
    int maxLen = 0;       // 结果：最长子数组长度
    
    for (int right = 0; right < nums.size(); ++right) {
        // 维护最大值队列
        while (!maxDeque.empty() && nums[right] >= nums[maxDeque.back()]) {
            maxDeque.pop_back();
        }
        maxDeque.push_back(right);
        
        // 维护最小值队列
        while (!minDeque.empty() && nums[right] <= nums[minDeque.back()]) {
            minDeque.pop_back();
        }
        minDeque.push_back(right);
        
        // 当窗口内最大值与最小值之差 > k 时，移动左边界
        while (nums[maxDeque.front()] - nums[minDeque.front()] > k) {
            if (maxDeque.front() == left) {
                maxDeque.pop_front();
            }
            if (minDeque.front() == left) {
                minDeque.pop_front();
            }
            left++;
        }
        
        // 更新最大长度
        maxLen = max(maxLen, right - left + 1);
    }
    
    return maxLen;
}

// 打印数组辅助函数
void printArray(const vector<int>& arr, const string& name) {
    cout << name << ": ";
    for (int num : arr) {
        cout << num << " ";
    }
    cout << endl;
}

int main() {
    // 测试场景1：滑动窗口最大值
    vector<int> nums1 = {1, 3, -1, -3, 5, 3, 6, 7};
    int k1 = 3;
    vector<int> maxWindow = maxSlidingWindow(nums1, k1);
    cout << "场景1：滑动窗口最大值" << endl;
    printArray(nums1, "输入数组");
    cout << "窗口大小: " << k1 << endl;
    printArray(maxWindow, "窗口最大值");
    cout << endl;
    
    // 测试场景2：滑动窗口最小值
    vector<int> nums2 = {4, 2, 1, 3, 6, 5};
    int k2 = 2;
    vector<int> minWindow = minSlidingWindow(nums2, k2);
    cout << "场景2：滑动窗口最小值" << endl;
    printArray(nums2, "输入数组");
    cout << "窗口大小: " << k2 << endl;
    printArray(minWindow, "窗口最小值");
    cout << endl;
    
    // 测试场景3：最长子数组（最大最小差 <= k）
    vector<int> nums3 = {8, 2, 4, 7};
    int k3 = 4;
    int maxLen = longestSubarrayWithDiff(nums3, k3);
    cout << "场景3：最长子数组（最大最小差 <= k）" << endl;
    printArray(nums3, "输入数组");
    cout << "k值: " << k3 << endl;
    cout << "最长子数组长度: " << maxLen << endl;
    
    return 0;
}

admin

1. 长度不超过 k 的最大子数组和
核心思想：结合前缀和与单调队列，将问题转化为 "在窗口内找到最小前缀和"
实现细节：
前缀和数组 prefix 表示前 i 个元素的和
单调队列维护前缀和的递增序列，确保能快速找到 prefix[j] - prefix 的最大值（i 和 j 的差不超过 k）
示例结果：数组 [1,-2,3,10,-4,7,2,-5] 中，长度不超过 4 的最大子数组和为 3+10-4+7=16
2. 任务调度中的资源峰值监控
核心场景：监控滑动窗口内的资源占用峰值，确保不超过系统阈值
实现细节：
单调队列（递减）维护窗口内的资源峰值
每次新任务加入时，移除窗口外的历史任务，并更新队列确保单调性
若任何窗口的峰值超过阈值，则返回调度失败
示例结果：资源序列 [3,1,4,2,5,3] 在窗口大小 3、阈值 4 时，因窗口 [4,2,5] 的峰值 5>4，返回不能调度
3. 0-1 BFS 优化（带权最短路径）
核心场景：求解网格中移动代价为 0 或 1 的最短路径（斜向移动代价 0，正交移动代价 1）
实现细节：
双端队列替代普通队列，代价 0 的节点从队头入队，代价 1 的节点从队尾入队
确保队列始终按距离递增，实现 O (n) 时间复杂度
示例结果：3x4 网格中从 (0,0) 到 (2,3) 的最短路径长度为 2（通过两次斜向移动）
4. 支持 O (1) 时间获取最大值的队列
核心功能：实现一个队列，支持入队、出队和获取最大值操作，均为 O (1) 时间
实现细节：
普通队列存储所有元素，单调队列（递减）维护最大值候选
入队时移除所有小于当前值的元素，出队时若弹出最大值则同步更新单调队列
示例结果：入队 3、1、4 后最大值为 4，出队 3 后最大值仍为 4，入队 2 后最大值保持 4，再出队 1 后最大值变为 2
总结
这些示例展示了单调队列在不同场景下的灵活性：
处理动态区间最值（如资源监控）
优化前缀和相关的子数组问题
加速特殊权重的图遍历（0-1 BFS）
实现高效的数据结构（带最大值的队列）

[C++] 纯文本查看 复制代码

#include <iostream>
#include <vector>
#include <deque>
#include <queue>
#include <climits>
#include <algorithm>

using namespace std;

/**
 * 应用1：长度不超过k的最大子数组和
 * 利用前缀和+单调队列，时间复杂度O(n)
 */
int maxSubarraySumWithMaxLength(const vector<int>& nums, int k) {
    int n = nums.size();
    if (n == 0 || k <= 0) return 0;
    
    vector<long long> prefix(n + 1, 0);  // 前缀和数组
    for (int i = 0; i < n; ++i) {
        prefix[i + 1] = prefix + nums;
    }
    
    deque<int> q;  // 单调队列，存储前缀和索引，维持前缀和递增
    int maxSum = INT_MIN;
    
    for (int j = 0; j <= n; ++j) {
        // 移除超出窗口范围的索引（窗口大小为j - i <= k）
        while (!q.empty() && j - q.front() > k) {
            q.pop_front();
        }
        
        // 当前前缀和 - 队列中最小前缀和 = 最大子数组和
        if (!q.empty()) {
            maxSum = max(maxSum, (int)(prefix[j] - prefix[q.front()]));
        }
        
        // 维护队列单调性：移除所有大于等于当前前缀和的元素
        // 因为对于未来的j'，prefix[j]比它们更小，是更优的选择
        while (!q.empty() && prefix[j] <= prefix[q.back()]) {
            q.pop_back();
        }
        
        q.push_back(j);
    }
    
    return maxSum;
}

/**
 * 应用2：任务调度中的资源峰值监控
 * 监控滑动窗口内的任务资源占用峰值，确保不超过阈值
 */
bool canScheduleTasks(const vector<int>& resources, int windowSize, int threshold) {
    deque<int> maxQ;  // 单调队列，维护窗口内资源占用峰值
    
    for (int i = 0; i < resources.size(); ++i) {
        // 移除超出窗口范围的元素
        if (!maxQ.empty() && i - maxQ.front() >= windowSize) {
            maxQ.pop_front();
        }
        
        // 维护队列单调性（递减）
        while (!maxQ.empty() && resources >= resources[maxQ.back()]) {
            maxQ.pop_back();
        }
        maxQ.push_back(i);
        
        // 窗口形成后检查是否超过阈值
        if (i >= windowSize - 1) {
            if (resources[maxQ.front()] > threshold) {
                return false;  // 资源超限，无法调度
            }
        }
    }
    
    return true;  // 所有窗口均满足条件
}

/**
 * 应用3：0-1 BFS优化（求解带0/1权重的最短路径）
 * 在网格中移动，上下左右移动代价为1，斜向移动代价为0，求最短路径
 */
int zeroOneBFS(const vector<vector<int>>& grid, pair<int, int> start, pair<int, int> end) {
    int m = grid.size();
    int n = grid[0].size();
    const int INF = 1e9;
    
    // 距离矩阵，初始化为无穷大
    vector<vector<int>> dist(m, vector<int>(n, INF));
    dist[start.first][start.second] = 0;
    
    // 双端队列：代价0的节点从队头入队，代价1的节点从队尾入队
    deque<pair<int, int>> dq;
    dq.push_back(start);
    
    // 8个方向：4个斜向（代价0），4个正交（代价1）
    vector<pair<int, int>> dirs = {{-1,-1}, {-1,1}, {1,-1}, {1,1},  // 斜向，代价0
                                   {-1,0}, {1,0}, {0,-1}, {0,1}};   // 正交，代价1
    
    while (!dq.empty()) {
        auto [x, y] = dq.front();
        dq.pop_front();
        
        // 到达终点，返回距离
        if (x == end.first && y == end.second) {
            return dist[x][y];
        }
        
        for (int i = 0; i < 8; ++i) {
            int nx = x + dirs.first;
            int ny = y + dirs.second;
            
            // 检查边界和可访问性（假设grid[j]=1表示可访问）
            if (nx >= 0 && nx < m && ny >= 0 && ny < n && grid[nx][ny] == 1) {
                int cost = (i < 4) ? 0 : 1;  // 前4个方向代价0，后4个代价1
                int newDist = dist[x][y] + cost;
                
                // 更新距离并加入队列
                if (newDist < dist[nx][ny]) {
                    dist[nx][ny] = newDist;
                    if (cost == 0) {
                        dq.push_front({nx, ny});  // 代价0放队头
                    } else {
                        dq.push_back({nx, ny});   // 代价1放队尾
                    }
                }
            }
        }
    }
    
    return -1;  // 无法到达终点
}

/**
 * 应用4：实现一个支持O(1)时间获取最大值的队列
 */
template <typename T>
class MaxQueue {
private:
    queue<T> q;           // 存储所有元素的普通队列
    deque<T> maxDeque;    // 单调队列，维护最大值
    
public:
    // 入队操作
    void push(T val) {
        q.push(val);
        // 移除队列中所有小于当前值的元素
        while (!maxDeque.empty() && val > maxDeque.back()) {
            maxDeque.pop_back();
        }
        maxDeque.push_back(val);
    }
    
    // 出队操作
    void pop() {
        if (q.empty()) return;
        T front = q.front();
        q.pop();
        // 如果出队的是最大值，同步更新单调队列
        if (front == maxDeque.front()) {
            maxDeque.pop_front();
        }
    }
    
    // 获取当前队列最大值
    T getMax() {
        if (maxDeque.empty()) {
            throw runtime_error("Queue is empty");
        }
        return maxDeque.front();
    }
    
    // 判断队列是否为空
    bool empty() {
        return q.empty();
    }
};

// 打印辅助函数
void printResult(int result, const string& msg) {
    cout << msg << result << endl;
}

void printBool(bool result, const string& msg) {
    cout << msg << (result ? "是" : "否") << endl;
}

int main() {
    // 测试应用1：长度不超过k的最大子数组和
    vector<int> nums1 = {1, -2, 3, 10, -4, 7, 2, -5};
    int k1 = 4;
    cout << "=== 应用1：长度不超过k的最大子数组和 ===" << endl;
    cout << "数组: ";
    for (int num : nums1) cout << num << " ";
    cout << ", k=" << k1 << endl;
    printResult(maxSubarraySumWithMaxLength(nums1, k1), "最大子数组和: ");
    cout << endl;
    
    // 测试应用2：任务调度资源监控
    vector<int> resources = {3, 1, 4, 2, 5, 3};
    int windowSize = 3, threshold = 4;
    cout << "=== 应用2：任务调度资源监控 ===" << endl;
    cout << "资源占用: ";
    for (int r : resources) cout << r << " ";
    cout << ", 窗口大小=" << windowSize << ", 阈值=" << threshold << endl;
    printBool(canScheduleTasks(resources, windowSize, threshold), "是否能调度所有任务: ");
    cout << endl;
    
    // 测试应用3：0-1 BFS
    vector<vector<int>> grid = {
        {1, 1, 1, 1},
        {1, 0, 0, 1},
        {1, 1, 1, 1}
    };
    pair<int, int> start = {0, 0};
    pair<int, int> end = {2, 3};
    cout << "=== 应用3：0-1 BFS最短路径 ===" << endl;
    cout << "网格大小: " << grid.size() << "x" << grid[0].size() << endl;
    cout << "起点: (" << start.first << "," << start.second << "), 终点: (" << end.first << "," << end.second << ")" << endl;
    printResult(zeroOneBFS(grid, start, end), "最短路径长度: ");
    cout << endl;
    
    // 测试应用4：带最大值的队列
    cout << "=== 应用4：带最大值的队列 ===" << endl;
    MaxQueue<int> mq;
    mq.push(3);
    mq.push(1);
    mq.push(4);
    cout << "入队3,1,4后，最大值: " << mq.getMax() << endl;  // 4
    mq.pop();
    cout << "出队后，最大值: " << mq.getMax() << endl;        // 4
    mq.push(2);
    cout << "入队2后，最大值: " << mq.getMax() << endl;       // 4
    mq.pop();
    cout << "出队后，最大值: " << mq.getMax() << endl;        // 2
    
    return 0;
}