从滑动窗口到优先队列：C++竞赛中的区间最值优化实战

在算法竞赛中，滑动窗口和优先队列是两个看似简单却暗藏玄机的重要工具。许多选手在掌握了基础概念后，面对实际问题的优化时仍会陷入困境。本文将以一个真实的竞赛案例为切入点，深入探讨如何用优先队列高效解决滑动窗口最值问题，帮助你在关键时刻不掉链子。

1. 滑动窗口算法的本质与常见陷阱

滑动窗口算法是处理数组/序列子区间问题的利器，其核心思想是维护一个动态变化的窗口，通过窗口的滑动来避免重复计算。但看似简单的思想背后，隐藏着不少容易踩中的陷阱。

典型应用场景 ：

• 固定长度子数组的最大/最小值
• 满足特定条件的最长子数组
• 多指针协同遍历问题

常见实现误区 ：

1. 窗口边界处理不当，导致数组越界
2. 未及时清理无效元素，影响判断逻辑
3. 时间复杂度分析错误，误以为O(n)实为O(n²)
4. 特殊边界条件考虑不周（如空窗口、全等元素等）

// 基础滑动窗口示例：求大小为k的窗口最大值
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
    vector<int> res;
    for (int i = 0; i <= nums.size() - k; ++i) {
        int max_val = INT_MIN;
        for (int j = i; j < i + k; ++j) {  // 内层循环导致O(n*k)复杂度
            max_val = max(max_val, nums[j]);
        }
        res.push_back(max_val);
    }
    return res;
}

上述代码虽然正确，但其O(n*k)的时间复杂度在面对1e5量级数据时会直接超时。这正是许多选手在竞赛中失分的关键原因——知道算法思想，却缺乏优化手段。

2. 优先队列：滑动窗口优化的利器

优先队列（priority_queue）能有效解决滑动窗口最值问题，将时间复杂度优化至O(n log n)。其核心优势在于：

• 自动维护元素优先级
• 快速访问最值元素
• 灵活的插入删除操作

C++中的优先队列实现 ：

#include <queue>
using namespace std;

// 默认大顶堆
priority_queue<int> pq1;  

// 小顶堆
priority_queue<int, vector<int>, greater<int>> pq2;  

// 自定义比较函数
struct Compare {
    bool operator()(const pair<int,int>& a, const pair<int,int>& b) {
        return a.first > b.first;  // 小顶堆
    }
};
priority_queue<pair<int,int>, vector<pair<int,int>>, Compare> pq3;

优先队列优化滑动窗口的关键点 ：

1. 同时存储元素值和其在原数组中的索引
2. 定期清理超出窗口范围的元素
3. 利用堆顶元素快速获取当前窗口最值

3. 实战：CCPC河南赛F题"Art for Last"的优先队列解法

让我们回到竞赛原题，看看如何用优先队列优雅解决这个问题。题目要求：给定数组a，找到所有长度为k的子区间，计算(区间最大值-区间最小值)*(区间首尾元素差)，然后取所有结果中的最小值。

解题步骤分解 ：

1. 排序原始数组
2. 计算相邻元素差值数组b
3. 使用优先队列维护滑动窗口最小值
4. 计算结果并取最小值

完整实现代码 ：

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;

const int N = 5e5 + 10;
int a[N], b[N];
int n, k;

ll solve() {
    sort(a + 1, a + 1 + n);
    for (int i = 1; i < n; ++i) b[i] = a[i + 1] - a[i];
    
    priority_queue<pii, vector<pii>, greater<pii>> pq;
    for (int i = 1; i < k - 1; ++i) pq.push({b[i], i});
    
    ll res = LLONG_MAX;
    for (int i = 1; i + k - 1 <= n; ++i) {
        int window_end = i + k - 2;
        if (window_end <= n - 1) pq.push({b[window_end], window_end});
        
        while (!pq.empty() && pq.top().second < i) pq.pop();
        
        if (!pq.empty()) {
            ll min_diff = pq.top().first;
            ll range_diff = a[i + k - 1] - a[i];
            res = min(res, min_diff * range_diff);
        }
    }
    return res;
}

int main() {
    cin >> n >> k;
    for (int i = 1; i <= n; ++i) cin >> a[i];
    cout << solve() << endl;
    return 0;
}

关键优化点解析 ：

1. 延迟删除 ：不立即删除无效元素，而是在访问堆顶时检查有效性
2. 索引追踪 ：存储元素原始位置，便于判断是否在窗口内
3. 时间复杂度 ：每个元素最多入队出队一次，整体O(n log n)

4. 同类问题扩展与举一反三

掌握了滑动窗口与优先队列的组合拳后，我们可以轻松解决一系列相似问题。以下是几个经典变种：

LeetCode 239. 滑动窗口最大值 ：

vector<int> maxSlidingWindow(vector<int>& nums, int k) {
    priority_queue<pair<int,int>> pq;
    vector<int> res;
    for (int i = 0; i < nums.size(); ++i) {
        pq.push({nums[i], i});
        while (pq.top().second <= i - k) pq.pop();
        if (i >= k - 1) res.push_back(pq.top().first);
    }
    return res;
}

Codeforces 问题变种 ：

• 求滑动窗口内第K小的元素
• 统计满足条件的滑动窗口数量
• 多维滑动窗口问题

性能对比表 ：

方法	时间复杂度	空间复杂度	适用场景
暴力法	O(n*k)	O(1)	小数据量(k<50)
优先队列	O(n log n)	O(n)	通用解法
单调队列	O(n)	O(k)	需要严格线性时间

调试技巧 ：

1. 打印优先队列内容辅助调试

void debug_pq(priority_queue<pii, vector<pii>, greater<pii>> pq) {
    while (!pq.empty()) {
        auto [val, idx] = pq.top();
        cout << "(" << val << "," << idx << ") ";
        pq.pop();
    }
    cout << endl;
}

2. 边界条件测试用例

• k=1
• k=n
• 所有元素相同
• 严格递增/递减序列

在实际编码时，建议先写出暴力解法确保逻辑正确，再逐步引入优先队列优化。同时要注意数据范围，防止整数溢出——这也是竞赛中常见的失分点。