给你两个整数 w
和 m
,以及一个整数数组 arrivals
,其中 arrivals[i]
表示第 i
天到达的物品类型(天数从 1 开始编号)。
物品的管理遵循以下规则:
i
,考虑天数范围为 [max(1, i - w + 1), i]
(也就是直到第 i
天为止最近的 w
天):
m
次。i
天保留该到达物品会导致其类型在该窗口中出现次数 超过 m
次,那么该物品必须被丢弃。返回为满足每个 w
天的窗口中每种类型最多出现 m
次,最少 需要丢弃的物品数量。
示例 1:
输入: arrivals = [1,2,1,3,1], w = 4, m = 2
输出: 0
解释:
m
次,因此保留。[1, 2, 1]
中物品 1 出现两次,符合限制。[1, 2, 1, 3]
中物品 1 出现两次,仍符合。[2, 1, 3, 1]
中物品 1 出现两次,依然有效。没有任何物品被丢弃,因此返回 0。
示例 2:
输入: arrivals = [1,2,3,3,3,4], w = 3, m = 2
输出: 1
解释:
[1, 2]
是可以的。[1, 2, 3]
中物品 3 出现一次。[2, 3, 3]
中物品 3 出现两次,允许。[3, 3, 3]
中物品 3 出现三次,超过限制,因此该物品必须被丢弃。[3, 4]
是可以的。第 5 天的物品 3 被丢弃,这是最少必须丢弃的数量,因此返回 1。
提示:
1 <= arrivals.length <= 105
1 <= arrivals[i] <= 105
1 <= w <= arrivals.length
1 <= m <= w