2026-02-09：使库存平衡的最少丢弃次数。用go语言，给定两个整数 w、m 和一个整数数组 arrivals（第 i 项表示第 i 天到达的物品种类，天数从 1 开始）。到达的每个物品可以选择保
2026-02-09：使库存平衡的最少丢弃次数。用go语言，给定两个整数 w、m 和一个整数数组 arrivals（第 i 项表示第 i 天到达的物品种类，天数从 1 开始）。到达的每个物品可以选择保留或当日丢弃（不能在之后丢弃）。
规则要求：对于任意一天 i，考察以该天为终点、长度为 w 的时间段（即从 max(1, i-w+1) 到 i 的最近 w 天）。在任意这样的时间段内，最终保留下来的物品中，每一种类型的数量不能超过 m。如果在第 i 天保留该天到来的物品会使得该类型在该时间段内的保留数量超出 m，则该物品必须在到达当天丢弃。
目标是找到一种丢弃/保留的决策，使得满足上述所有窗口约束的前提下，被丢弃的物品总数最少，并返回这个最小丢弃数。
1 <= arrivals.length <= 100000。
1 <= arrivals[i] <= 100000。
1 <= w <= arrivals.length。
1 <= m <= w。
输入： arrivals = [1,2,3,3,3,4], w = 3, m = 2。
输出： 1。
解释：
第 1 天，物品 1 到达。我们保留它。
第 2 天，物品 2 到达，窗口 [1, 2] 是可以的。
第 3 天，物品 3 到达，窗口 [1, 2, 3] 中物品 3 出现一次。
第 4 天，物品 3 到达，窗口 [2, 3, 3] 中物品 3 出现两次，允许。
第 5 天，物品 3 到达，窗口 [3, 3, 3] 中物品 3 出现三次，超过限制，因此该物品必须被丢弃。
第 6 天，物品 4 到达，窗口 [3, 4] 是可以的。
第 5 天的物品 3 被丢弃，这是最少必须丢弃的数量，因此返回 1。
题目来自力扣3679。
问题解决步骤分解
1. 初始化与准备
- 函数首先初始化一个空的哈希表
cnt，用于实时跟踪当前滑动窗口内各种物品类型的保留数量。哈希表的键（key）是物品种类编号，值（value）是该种类在当前窗口内的出现次数。 - 初始化丢弃计数器
ans为 0，用于累计最终需要丢弃的物品数量。
2. 遍历每一天的物品
- 函数通过一次顺序遍历来处理每一天（索引
i从 0 开始，对应第i+1天）到达的物品x（即arrivals[i]）。 - 对于每一天，处理逻辑分为两个主要部分：处理新到达物品和管理窗口左边界。
3. 处理新到达物品（决定保留或丢弃）
- 在物品
x进入窗口时，代码会检查当前窗口内该物品已有的保留数量cnt[x]。 - 决策逻辑：
- 如果
cnt[x]已经等于m（即该物品在窗口内的数量已达到上限），那么新到达的这个物品x必须被丢弃。- 丢弃操作：将
arrivals[i]的值置为0（这是一个关键技巧，用0标记该位置的物品已被丢弃，因为原物品编号都是正整数，0不会与任何有效种类冲突）。 - 丢弃计数器
ans加 1。
- 丢弃操作：将
- 如果
cnt[x]小于m，则这个新物品可以被安全地保留。此时，哈希表cnt中对应物品x的计数加 1。
- 如果
4. 滑动窗口的维护（左边界物品出窗）
- 在处理好新物品后，代码需要检查是否有物品需要从当前窗口中“移出”。这是通过计算窗口的左边界索引
left来实现的：left = i - w + 1。 - 移出逻辑：
- 只有当
left >= 0时，才意味着窗口已经完整（长度达到了w），并且有物品（即第left天到达的物品）需要离开窗口。 - 对于要离开窗口的物品（其种类是
arrivals[left]），无论它当初是被保留（值为正数）还是被丢弃（值被置为0），都统一在哈希表cnt中将其对应种类的计数减 1。 - 关键点：这个“出窗”操作是前瞻性的。它发生在索引为
i的循环中，但实际上是在为下一个循环（即下一天i+1）准备一个正确的窗口状态。因为当处理下一天i+1时，窗口的左边界就是i+1-w = left+1，所以需要提前将第left天（即即将离开窗口的那一天）的影响移除。
- 只有当
5. 遍历结束与结果返回
- 当循环遍历完
arrivals数组中的所有天数后，累计的丢弃次数ans就是满足所有窗口约束下的最小丢弃数量，将其作为结果返回。
复杂度分析
-
总的时间复杂度：O(n)。
- 函数仅对长度为
n（n = len(arrivals)）的数组进行了一次顺序遍历。在遍历的每一步中，对哈希表cnt的查询、插入和修改操作在平均情况下都可以视为 O(1) 的时间复杂度。因此，总体时间复杂度是线性的 O(n)。
- 函数仅对长度为
-
总的额外空间复杂度：O(n)。
- 主要的额外空间消耗来自两个方面：
- 哈希表
cnt：在最坏情况下，窗口内可能包含所有不同的物品类型。由于物品种类编号的范围很大（最大可达 10^5），但实际存储在cnt中的键的数量取决于当前窗口内出现的不重复物品种类数。窗口最大长度为w，因此哈希表最多需要 O(w) 的空间。由于w <= n，这部分可记为 O(n)。 - 输入的
arrivals数组本身被修改了，但这通常不计入“额外”空间，因为它是输入数据。如果考虑对输入数据的修改，那么算法是原地（in-place） 的，没有因此消耗额外空间。
- 哈希表
- 综合来看，空间复杂度主要取决于哈希表，为 O(n)。
- 主要的额外空间消耗来自两个方面：
通过上述的单次遍历和巧妙的哈希表计数管理，该算法高效地解决了问题，其核心在于实时维护窗口状态并即时做出最优的丢弃决策，确保了在满足约束的同时最小化丢弃总数。
Go完整代码如下：
package main
import (
"fmt"
)
func minArrivalsToDiscard(arrivals []int, w, m int) (ans int) {
cnt := map[int]int{}
for i, x := range arrivals {
// x 进入窗口
if cnt[x] == m { // x 的个数已达上限
// 注意 x 在未来要离开窗口，但由于已经丢弃，不能在离开窗口时修改 cnt
// 这里直接置为 0，未来离开窗口就是 cnt[0]--，不影响答案
arrivals[i] = 0 // 丢弃 arrivals[i]
ans++
} else {
cnt[x]++
}
// 左端点元素离开窗口，为下一个循环做准备
left := i + 1 - w
if left >= 0 {
cnt[arrivals[left]]--
}
}
return
}
func main() {
arrivals := []int{1, 2, 3, 3, 3, 4}
w := 3
m := 2
result := minArrivalsToDiscard(arrivals, w, m)
fmt.Println(result)
}
Python完整代码如下：
# -*-coding:utf-8-*-
from typing import List
def min_arrivals_to_discard(arrivals: List[int], w: int, m: int) -> int:
cnt = {} # 计数器字典
ans = 0
for i, x in enumerate(arrivals):
# x 进入窗口
if cnt.get(x, 0) == m: # x 的个数已达上限
# 注意 x 在未来要离开窗口，但由于已经丢弃，不能在离开窗口时修改 cnt
# 这里直接置为 0，未来离开窗口就是 cnt[0]--，不影响答案
arrivals[i] = 0 # 丢弃 arrivals[i]
ans += 1
else:
cnt[x] = cnt.get(x, 0) + 1
# 左端点元素离开窗口，为下一个循环做准备
left = i + 1 - w
if left >= 0:
left_val = arrivals[left]
cnt[left_val] = cnt.get(left_val, 0) - 1
return ans
if __name__ == "__main__":
arrivals = [1, 2, 3, 3, 3, 4]
w = 3
m = 2
result = min_arrivals_to_discard(arrivals, w, m)
print(result)
C++完整代码如下：
#include 
