算法刷题系列（六十三）：滑动窗口三道题——从定长统计到动态维护

算法刷题系列（六十三）：滑动窗口三道题——从定长统计到动态维护

第十七篇讲了窗口不变量与单调性。本篇把旧的三个窗口练习整理成一组递进例题：

1. 定长窗口最大平均数：窗口统计量只需加进、减出。
2. 一次技巧最大化满意顾客数：先计算固定收益，再在窗口中优化可挽回部分。
3. 窗口第 x 小负数：值域有限时，用频数表维护次序统计。

三题都有固定窗口长度，但窗口内部状态不同，体现了“窗口模板不变，维护的信息按问题变化”。

一、固定长度最大平均数

长度固定为 k 时，最大平均数等价于最大窗口和，因为除数 k 对每个候选都相同。

窗口从 [0, k) 移到 [1, k + 1) 时，只需减去离开窗口的值、加上新进入的值。总扫描时间从每个窗口重新求和的 O(nk) 降为 O(n)。

Java

public static double maxAverage(int[] values, int k) {
    if (values == null || k <= 0 || k > values.length) {
        throw new IllegalArgumentException("require 1 <= k <= values.length");
    }
    long window = 0;
    for (int i = 0; i < k; i++) {
        window += values[i];
    }
    long best = window;
    for (int right = k; right < values.length; right++) {
        window += (long) values[right] - values[right - k];
        best = Math.max(best, window);
    }
    return (double) best / k;
}

Python

def max_average(values: list[int], k: int) -> float:
    if values is None or k <= 0 or k > len(values):
        raise ValueError("require 1 <= k <= len(values)")
    window = sum(values[:k])
    best = window
    for right in range(k, len(values)):
        window += values[right] - values[right - k]
        best = max(best, window)
    return best / k

assert max_average([1, 12, -5, -6, 50, 3], 4) == 12.75
assert max_average([-4, -2, -8], 1) == -2

初始化最大值为第一个真实窗口，而非 0，才能正确处理全负数。

二、一次技巧最大化满意顾客数

每分钟顾客分成两类：

• 老板本来不生气的分钟：顾客一定满意，先累计为 base；
• 老板生气的分钟：顾客目前不满意，但若技巧覆盖该分钟就可挽回，计入 recoverable。

技巧只能覆盖长度为 k 的一个连续区间，所以对“可挽回顾客数”做定长窗口最大化。最终结果是：

base + 窗口内可挽回人数的最大值

Java

public static long maxSatisfied(int[] customers, int[] grumpy, int minutes) {
    if (customers == null || grumpy == null
            || customers.length != grumpy.length
            || minutes < 1 || minutes > customers.length) {
        throw new IllegalArgumentException("invalid input lengths or window");
    }
    long base = 0;
    long recoverable = 0;
    long bestRecoverable = 0;
    for (int i = 0; i < customers.length; i++) {
        if (grumpy[i] == 0) {
            base += customers[i];
        } else {
            recoverable += customers[i];
        }
        if (i >= minutes && grumpy[i - minutes] == 1) {
            recoverable -= customers[i - minutes];
        }
        if (i >= minutes - 1) {
            bestRecoverable = Math.max(bestRecoverable, recoverable);
        }
    }
    return base + bestRecoverable;
}

Python

def max_satisfied(customers: list[int], grumpy: list[int], minutes: int) -> int:
    if customers is None or grumpy is None or len(customers) != len(grumpy):
        raise ValueError("customers and grumpy must have equal lengths")
    if not customers or minutes < 1 or minutes > len(customers):
        raise ValueError("require 1 <= minutes <= len(customers)")

    base = sum(count for count, angry in zip(customers, grumpy) if not angry)
    recoverable = 0
    best_recoverable = 0
    for index, (count, angry) in enumerate(zip(customers, grumpy)):
        if angry:
            recoverable += count
        if index >= minutes and grumpy[index - minutes]:
            recoverable -= customers[index - minutes]
        if index >= minutes - 1:
            best_recoverable = max(best_recoverable, recoverable)
    return base + best_recoverable

assert max_satisfied(
    [1, 0, 1, 2, 1, 1, 7, 5],
    [0, 1, 0, 1, 0, 1, 0, 1],
    3,
) == 16
assert max_satisfied([1], [0], 1) == 1

窗口维护的不是总顾客数，而是“因技巧能新增满意”的顾客数；把固定收益和可变收益分离，会让状态更容易验证。

三、每个窗口的第 x 小负数

若数值范围很小，例如 [-50, 50]，可以用频数数组代替排序。每次滑动时更新两个计数；查询时从最小的负值向上累计频次，累计数量首次达到 x 的值就是第 x 小，否则答案为 0。

设值域宽度为 U，每个窗口查询需 O(U)；整体为 O(nU)。当 U 很小且固定时很实用；若值域很大，应使用有序树、平衡树或其他次序统计结构。

Java

public static int[] windowBeauty(int[] values, int k, int x) {
    if (values == null || k <= 0 || k > values.length || x <= 0 || x > k) {
        throw new IllegalArgumentException("invalid window or rank");
    }
    int[] count = new int[101]; // 值域限定为 [-50, 50]
    int[] answer = new int[values.length - k + 1];
    for (int i = 0; i < values.length; i++) {
        if (values[i] < -50 || values[i] > 50) {
            throw new IllegalArgumentException("value outside [-50, 50]");
        }
        count[values[i] + 50]++;
        if (i >= k) {
            count[values[i - k] + 50]--;
        }
        if (i >= k - 1) {
            int rank = x;
            for (int value = -50; value < 0; value++) {
                rank -= count[value + 50];
                if (rank <= 0) {
                    answer[i - k + 1] = value;
                    break;
                }
            }
        }
    }
    return answer;
}

Python

def window_beauty(values: list[int], k: int, x: int) -> list[int]:
    if values is None or k <= 0 or k > len(values) or x <= 0 or x > k:
        raise ValueError("invalid window or rank")
    if any(value < -50 or value > 50 for value in values):
        raise ValueError("values must be in [-50, 50]")

    counts = [0] * 101
    answer = []
    for index, value in enumerate(values):
        counts[value + 50] += 1
        if index >= k:
            counts[values[index - k] + 50] -= 1
        if index >= k - 1:
            rank = x
            beauty = 0
            for candidate in range(-50, 0):
                rank -= counts[candidate + 50]
                if rank <= 0:
                    beauty = candidate
                    break
            answer.append(beauty)
    return answer

assert window_beauty([1, -1, -3, -2, 3], 3, 2) == [-1, -2, -2]
assert window_beauty([3, 2, 1], 2, 2) == [0, 0]

四、三题共用的窗口不变量

处理第 right 个元素后，状态必须准确表示窗口 [right-k+1, right]：

• 最大平均数：窗口和；
• 满意顾客：固定满意数 + 窗口内可挽回数；
• 美丽值：窗口中每个取值的频数。

先加入新元素、移除越界旧元素，再读取答案；若调整顺序，必须重新推导窗口内的元素范围，避免偏一位。

五、常见错误

1. 用 int 保存可能很大的窗口和：Java 选择足够宽的类型。
2. 全负数组用 0 初始化最大值：会错误地返回 0。
3. 把技巧覆盖区间内所有顾客都计为新增收益：只累计原本不满意的顾客。
4. 删除频数时删错下标：离开窗口的是 right-k。
5. 窗口次序统计忽略值域假设：计数数组只能在值域有限且已验证时使用。

与系列其他篇章的连接

通用窗口前提和可变长度窗口见第 17 篇；若窗口内要动态维护最值，可进一步学习单调队列；若要维护任意分位数且值域大，则需要有序统计结构。

小结

固定窗口只规定了边界如何移动，真正的算法状态由题目决定。窗口和、可挽回收益、值域频数都可以在进入与离开时增量更新，避免对每个窗口重新扫描。