最高频元素的频数

记住「排序 → 抬平代价 = 最大值×长度 − 窗口和 → 代价超 k 就左缩、记最长」,下面每一格都在套它。

第一步排序。排完序相邻的数才挨在一起,抬平代价最小,滑动窗口也才能稳稳伸缩。下面窗口从空开始,右指针一格格扩。

右指针到第 0 位(值 1)。把窗口里 1 个数都抬到最大的 1,要花 1×1 减去窗口和 1,也就是 0 次操作。没超过 k=10,这段抬得平。

窗口 [0, 0] 抬平只要 0 次(≤10),长度 1。比之前还长,最高频数刷新成 1。

右指针到第 1 位(值 2)。把窗口里 2 个数都抬到最大的 2,要花 2×2 减去窗口和 3,也就是 1 次操作。没超过 k=10,这段抬得平。

窗口 [0, 1] 抬平只要 1 次(≤10),长度 2。比之前还长,最高频数刷新成 2。

右指针到第 2 位(值 3)。把窗口里 3 个数都抬到最大的 3,要花 3×3 减去窗口和 6,也就是 3 次操作。没超过 k=10,这段抬得平。

窗口 [0, 2] 抬平只要 3 次(≤10),长度 3。比之前还长,最高频数刷新成 3。

右指针到第 3 位(值 4)。把窗口里 4 个数都抬到最大的 4,要花 4×4 减去窗口和 10,也就是 6 次操作。没超过 k=10,这段抬得平。

窗口 [0, 3] 抬平只要 6 次(≤10),长度 4。比之前还长,最高频数刷新成 4。

右指针到第 4 位(值 5)。把窗口里 5 个数都抬到最大的 5,要花 5×5 减去窗口和 15,也就是 10 次操作。没超过 k=10,这段抬得平。

窗口 [0, 4] 抬平只要 10 次(≤10),长度 5。比之前还长,最高频数刷新成 5。

右指针到第 5 位(值 6)。把窗口里 6 个数都抬到最大的 6,要花 6×6 减去窗口和 21,也就是 15 次操作。它 > k=10(红),操作不够,下一步得左缩。

左指针右移 1 步、把移出的数从和里减掉,代价降到 10(≤10)。现在窗口 [1, 5] 能全抬成 6、长度 5。没超过已记的最长 5,保持。

右指针到第 6 位(值 7)。把窗口里 6 个数都抬到最大的 7,要花 7×6 减去窗口和 27,也就是 15 次操作。它 > k=10(红),操作不够,下一步得左缩。

左指针右移 1 步、把移出的数从和里减掉,代价降到 10(≤10)。现在窗口 [2, 6] 能全抬成 7、长度 5。没超过已记的最长 5,保持。

右指针到第 7 位(值 8)。把窗口里 6 个数都抬到最大的 8,要花 8×6 减去窗口和 33,也就是 15 次操作。它 > k=10(红),操作不够,下一步得左缩。

左指针右移 1 步、把移出的数从和里减掉,代价降到 10(≤10)。现在窗口 [3, 7] 能全抬成 8、长度 5。没超过已记的最长 5,保持。

右指针到第 8 位(值 9)。把窗口里 6 个数都抬到最大的 9,要花 9×6 减去窗口和 39,也就是 15 次操作。它 > k=10(红),操作不够,下一步得左缩。

左指针右移 1 步、把移出的数从和里减掉,代价降到 10(≤10)。现在窗口 [4, 8] 能全抬成 9、长度 5。没超过已记的最长 5,保持。

右指针到第 9 位(值 12)。把窗口里 6 个数都抬到最大的 12,要花 12×6 减去窗口和 47,也就是 25 次操作。它 > k=10(红),操作不够,下一步得左缩。

左指针右移 3 步、把移出的数从和里减掉,代价降到 7(≤10)。现在窗口 [7, 9] 能全抬成 12、长度 3。没超过已记的最长 5,保持。

扫完全程,能在 10 次操作内抬成同一个值的最长窗口长 5,所以最高频数是 5。排序加滑窗,一遍就找到了,不用枚举抬哪个值。

边界:k=0 时数排序后本来相等的段;单元素是 1。

面试常考:代价单调性(可滑窗的前提)+ 最长窗口长度即最高频数。