P3251. 找出通过车辆最多颜色

解题思路

本题明确地指出，时间窗口的长度为 N，所以考虑使用 固定滑窗 来解决问题。

由于在滑窗内需要统计各种颜色车辆的数目，所以我们可以用 哈希表 来统计元素频率。特别地，由于题目告诉我们车辆颜色有且只有 0, 1, 2 三种，所以我们可以更加简单地用一个列表 windows_colors 来代替哈希表。

对于固定滑窗，我们需要考虑滑窗和答案的初始化。我们需要以第一个窗口，即 colors[0:N] 这个窗口的情况来初始化 windows_colors = [0, 0, 0]。然后遍历 colors[0:N] 中的颜色，将其统计在 windows_colors 中。而答案变量 ans 的初始化，即为第一个固定滑窗中的 最大值。

然后我们思考 滑窗三问三答。

滑窗三问

• Q1：对于每一个右指针 right 所指的元素 right_color，做什么操作？
• Q2：什么时候要令左指针 left 右移？对于 left 所指的元素 left_color，要做什么操作？
• Q3：什么时候进行 ans 的更新？如何更新？

滑窗三答

• A1：将 right_color 在 windows_colors 中的统计次数 +1
• A2：在固定滑窗中，left 始终为 right - N，同时需要将 left_color 在 windows_colors 中的统计次数 -1
• A3：做完 windows_colors 的更新后，取其中 最大值 和当前 ans 比较并更新。

复杂度分析 设 n 为车流颜色序列 colors 的长度，N 为时间窗口的长度。

• 时间复杂度：O(n)。初始化第一个窗口需要遍历前 N 个元素做计数，是 O(N)；之后右指针从 N 走到 n-1，每一步只做三件事：新进窗口的颜色计数加一、滑出窗口的颜色计数减一、再在只有 3 个格子的计数数组里取最大值并更新 ans。由于题目中颜色只有 0、1、2 三种，取最大值是固定 3 次比较的常数操作，所以每步都是 O(1)，整个滑窗过程就是一趟对序列的线性扫描，瓶颈也在这趟扫描上。
• 空间复杂度：O(1)（不计输入数组）。计数结构 windows_colors 固定只有 3 个元素，另外只有 ans、left 等常数个变量。

正因为颜色种类固定为 3，才能用长度为 3 的小数组代替通用哈希表，并把「查窗口内最多的颜色数」压成常数时间；如果颜色种类为 C，每步取最大值的代价会变成 O(C)，总时间为 O(n×C)。