题解 | 使库存平衡的最少丢弃数
题目：
题干分析：
题干为我们说明了一个类似流水线上的物品管理规定,内容拟似如下:
- 每天流水线上会下来一个产品,类型编号为arrivals[i].
- 每天的产品我们必须在当天决定选择保留或者丢弃.
- 工厂要求连续w天内下线的产品同一型号最多出现m次(可理解为库存最值),超过则当天产品必须丢弃.
算法思路：
题目已经几乎明示我们使用滑动窗口进行解题,剩下的便是使用哈希表当作类型计数器,然后直接模拟即可.
需要注意的是丢弃的商品要做好标记,不要没有计入计数滑出窗口时反倒出了窗口导致计数失灵.
实现代码：
int minArrivalsToDiscard(vector<int>& arrivals, int w, int m) {
if (m >= w) return 0;
unordered_map<int, int> cnt;// 计数器
int ans = 0;
for (int i = 0; i < arrivals.size(); ++i) {
int x = arrivals[i];
++cnt[x];
if (cnt[x] > m) {
--cnt[x];
++ans;
arrivals[i] = 0; // 标记为0,防止意外出窗口(1 <= arrivals[i])
}
if (i >= w - 1 && arrivals[i - w + 1]) {
--cnt[arrivals[i - w + 1]];
}
}
return ans;
}
复杂度分析：
- 时间复杂度: 针对每个数组元素进行操作,总时间复杂度为O(n);
- 空间复杂度: 哈希表计数消耗额外空间站主体,总空间复杂度为O(k),k为arrivals数组中编号的种数.
查看18道真题和解析