每日c/c++题 备战蓝桥杯（洛谷P1440 求m区间内的最小值 详解（单调队列优化））

洛谷P1440 求m区间最小值：单调队列优化详解（从暴力到O(n)的蜕变）

tags: [算法, 数据结构, 滑动窗口, 洛谷, C++]

引言

在处理序列数据的区间查询问题时，暴力枚举往往难以应对大规模数据。本文以洛谷P1440为切入点，深入剖析如何通过单调队列数据结构，将时间复杂度从O(nm)优化至O(n)，完美解决百万级数据下的实时查询需求。

题目解析

问题定义
给定长度为n的序列和滑动窗口大小m，要求输出每个窗口内的最小值。当m>n时输出全0。

输入格式

• 第一行：两个整数n, m
• 第二行：n个整数表示序列元素

输出格式
输出n-m+1行，每行一个整数表示对应窗口的最小值

数据范围

• 1 ≤ m ≤ n ≤ 2×10⁶
• 元素值域：1 ≤ a_i ≤ 10⁹

算法演进：从暴力到优化

暴力解法（O(nm)）

for (int i=0; i<=n-m; i++) {
    int min_val = INF;
    for (int j=i; j<i+m; j++) {
        min_val = min(min_val, a[j]);
    }
    cout << min_val << endl;
}

缺陷：当n=2×10⁶时，总操作次数达4×10¹²次，远超时限。

单调队列优化（O(n)）

核心思想：维护一个双端队列，使其满足：

1. 队列元素对应值严格单调递增
2. 队首元素始终是当前窗口的最小值下标
3. 自动清理失效元素（超出窗口范围或被新元素"淘汰"）

代码实现与优化

完整代码（C++）

#include <iostream>
using namespace std;

const int MAXN = 2e6 + 5;
int a[MAXN];       // 原始数组（1-based）
int deque[MAXN];    // 手动实现双端队列
int front = 0, rear = -1;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n, m;
    cin >> n >> m;
    
    // 特殊情况处理
    if (m > n) {
        for (int i=0; i<n; i++) cout << "0\n";
        return 0;
    }

    for (int i=1; i<=n; i++) cin >> a[i];

    // 初始化队列（前m个元素）
    for (int i=1; i<=m; i++) {
        while (rear >= front && a[deque[rear]] >= a[i]) rear--;
        deque[++rear] = i;
    }

    // 处理剩余窗口
    for (int i=m+1; i<=n; i++) {
        cout << a[deque[front]] << "\n";
        
        // 移除失效队首
        while (deque[front] <= i - m) front++;
        
        // 维护单调性
        while (rear >= front && a[deque[rear]] >= a[i]) rear--;
        deque[++rear] = i;
    }
    
    // 输出最后一个窗口
    cout << a[deque[front]] << "\n";

    return 0;
}

关键优化点

1. 输入优化

   • 关闭同步流ios::sync_with_stdio(false)
   • 解除cin绑定cin.tie(nullptr)
     使输入速度提升3-5倍

2. 数组下标处理

   • 采用1-based索引，避免处理0号元素的特殊情况
   • 显式处理m>n的边界条件

3. 空间优化

   • 使用静态数组模拟双端队列，避免STL动态内存分配的开销
   • 相比STL deque，内存访问更连续，缓存命中率更高

算法流程详解

以输入序列[1,3,2,4,5], m=3为例：

执行流程：

1. 初始化阶段：处理前m个元素，构建初始单调队列
2. 滑动阶段：
   • 输出当前窗口最小值（队首元素）
   • 移除窗口左边界外的元素
   • 从队尾开始移除所有≥新元素的元素，保持单调性
   • 将新元素下标加入队列

复杂度分析

常见问题解决方案

1. 队列为空检查
   通过while (rear >= front)保证队列操作安全性

2. 重复元素处理
   使用>=而非>判断，确保相同值元素正确弹出，维护严格单调性

3. 窗口左移边界
   当deque[front] <= i - m时，队首元素已不在当前窗口

扩展应用场景

1. 滑动窗口最大值：修改比较符号方向即可
2. 动态规划优化：如最大矩形面积问题（LeetCode 84）
3. 实时流处理：维护最近m条记录的统计信息

总结

单调队列通过三个核心操作：

• 失效元素清理：保证窗口有效性
• 单调性维护：确保最小值在队首
• 元素淘汰机制：避免无效比较

实现了时间复杂度的质的飞跃。该算法思想是解决滑动窗口类问题的基石，掌握其精髓对算法进阶至关重要。建议配合LeetCode 239（滑动窗口最大值）进行巩固练习。

“优秀的算法工程师不是在发明新算法，而是在合适场景选择最优雅的工具。” —— 本题解正是对这一理念的实践诠释。