23. 数组的滑动窗口：固定窗口与可变窗口的最大值、最小值问题

滑动窗口，这个名字听起来挺唬人。说白了，就是在一个数组上，用一个「窗口」框住一段连续的元素，然后让这个窗口滑起来。你想想看，是不是很像我们看手机上的新闻列表，手指一划，新内容进来，旧内容出去。

我刚开始学这个的时候，总觉得这玩意儿不就是两层循环嘛，有啥好讲的？后来在项目中处理实时传感器数据流，才明白它的威力。嗯，今天我们就把它彻底讲透。

23.1 什么是滑动窗口？

滑动窗口分两种：固定窗口和可变窗口。

• 固定窗口：窗口大小不变，比如每次看3个元素，从左往右滑。
• 可变窗口：窗口大小可以伸缩，比如找「和大于某个值的最短子数组」。

我个人习惯把固定窗口想象成「火车车厢」，每节车厢长度一样，一节一节往前开。可变窗口则像「伸缩门」，根据需要拉长或缩短。

23.2 固定窗口的最大值问题

先来个经典题：给定一个数组和一个窗口大小 k，求每个窗口的最大值。

举个例子：arr = [1, 3, -1, -3, 5, 3, 6, 7]，k = 3。

窗口依次为：
[1, 3, -1] → 最大值 3
[3, -1, -3] → 最大值 3
[-1, -3, 5] → 最大值 5
... 以此类推

最笨的方法是什么？每个窗口都遍历一遍找最大值。时间复杂度 O(n*k)，数据量一大就崩了。

我在项目中遇到过类似场景：处理每秒上千条的股票行情数据，每个窗口都要算最高价。用暴力法？CPU直接报警。

那怎么办？用双端队列（deque）。

双端队列解法

思路很简单：队列里只保留「有可能成为最大值的元素」的下标。

• 新元素进来时，把队列尾部比它小的元素全部干掉（因为它们永远没机会了）
• 窗口滑动时，检查队首元素是否已经滑出窗口，如果是，弹出
• 每次窗口满时，队首就是当前窗口的最大值

#include <stdio.h>
#include <stdlib.h>

#define MAX_N 100000

// 双端队列结构
typedef struct {
    int data[MAX_N];
    int front, rear;
} Deque;

void init(Deque *q) {
    q->front = 0;
    q->rear = 0;
}

int isEmpty(Deque *q) {
    return q->front == q->rear;
}

void push_back(Deque *q, int val) {
    q->data[q->rear++] = val;
}

int pop_front(Deque *q) {
    return q->data[q->front++];
}

int pop_back(Deque *q) {
    return q->data[--q->rear];
}

int get_front(Deque *q) {
    return q->data[q->front];
}

int get_back(Deque *q) {
    return q->data[q->rear - 1];
}

// 滑动窗口最大值
void slidingWindowMax(int *arr, int n, int k) {
    Deque dq;
    init(&dq);
    
    for (int i = 0; i < n; i++) {
        // 移除队尾比当前元素小的元素
        while (!isEmpty(&dq) && arr[get_back(&dq)] <= arr[i]) {
            pop_back(&dq);
        }
        push_back(&dq, i);
        
        // 移除滑出窗口的队首元素
        if (get_front(&dq) <= i - k) {
            pop_front(&dq);
        }
        
        // 窗口满时输出结果
        if (i >= k - 1) {
            printf("%d ", arr[get_front(&dq)]);
        }
    }
    printf("\n");
}

int main() {
    int arr[] = {1, 3, -1, -3, 5, 3, 6, 7};
    int n = sizeof(arr) / sizeof(arr[0]);
    int k = 3;
    
    slidingWindowMax(arr, n, k);
    // 输出：3 3 5 5 6 7
    
    return 0;
}

23.3 固定窗口的最小值问题

最大值会了，最小值就是反过来。把比较符号换一下就行：

// 滑动窗口最小值
void slidingWindowMin(int *arr, int n, int k) {
    Deque dq;
    init(&dq);
    
    for (int i = 0; i < n; i++) {
        // 移除队尾比当前元素大的元素（注意这里是大于）
        while (!isEmpty(&dq) && arr[get_back(&dq)] >= arr[i]) {
            pop_back(&dq);
        }
        push_back(&dq, i);
        
        if (get_front(&dq) <= i - k) {
            pop_front(&dq);
        }
        
        if (i >= k - 1) {
            printf("%d ", arr[get_front(&dq)]);
        }
    }
    printf("\n");
}

你看，就改了一个符号。最大值是干掉比当前小的，最小值是干掉比当前大的。逻辑完全对称。

23.4 可变窗口：最长/最短子数组问题

可变窗口就更有意思了。它没有固定大小，而是根据条件动态调整。

经典问题：找出和大于等于 target 的最短子数组。

思路：用两个指针 left 和 right 维护窗口。right 不断右移扩大窗口，当窗口内的和满足条件时，尝试移动 left 缩小窗口，记录最小长度。

int minSubArrayLen(int target, int *arr, int n) {
    int left = 0, sum = 0;
    int minLen = n + 1;  // 初始化为一个不可能的大值
    
    for (int right = 0; right < n; right++) {
        sum += arr[right];
        
        // 满足条件时，尝试缩小窗口
        while (sum >= target) {
            int curLen = right - left + 1;
            if (curLen < minLen) {
                minLen = curLen;
            }
            sum -= arr[left];
            left++;
        }
    }
    
    return (minLen == n + 1) ? 0 : minLen;
}

我曾经在做一个网络流量监控系统时，需要找出「连续时间窗口内流量超过阈值的最短时间段」。用的就是这套逻辑。当时数据量很大，O(n) 的复杂度才能扛得住。

23.5 滑动窗口的通用模板

我总结了一个通用模板，基本上所有滑动窗口问题都能套：

int slidingWindow(int *arr, int n, int k) {
    int left = 0;
    // 初始化窗口状态，比如 sum、count 等
    
    for (int right = 0; right < n; right++) {
        // 1. 将 arr[right] 加入窗口，更新状态
        
        // 2. 根据条件调整 left（固定窗口不需要这步）
        while (/* 窗口需要缩小的条件 */) {
            // 移除 arr[left]，更新状态
            left++;
        }
        
        // 3. 如果窗口满足条件，更新答案
        // 固定窗口：right - left + 1 == k 时
        // 可变窗口：条件满足时
    }
    
    return 答案;
}

你想想看，不管是最大值、最小值、和、乘积、字符种类，本质上都是这个框架。区别只在于「状态」是什么，以及「条件」怎么判断。

23.6 知识体系图

下面这张图帮你理清滑动窗口的整个知识脉络：

23.7 避坑指南

我踩过的坑，你最好别踩：

• 边界条件：窗口大小 k 大于数组长度怎么办？返回空还是返回整个数组的最大值？提前想好。
• 下标越界：双端队列里存的是下标，pop 的时候一定要检查队列是否为空。我曾经因为这个在线上环境出了 bug，排查了半天。
• 可变窗口的 while 循环：一定要确保循环能终止。比如 sum 减去 arr[left] 后，left 要递增，不然就死循环了。
• 数据类型：如果数组元素很大，sum 可能会溢出。用 long long 或者更大的类型。

滑动窗口就这么点东西。固定窗口用双端队列，可变窗口用双指针。掌握了这两个套路，面试中遇到滑动窗口的题，基本就是秒杀。

---

公众号：蓝海资料掘金营，微信 deep3321