1052. 爱生气的书店老板题目描述给定两个数组customers和grumpy其中customers[i]表示第i分钟来的顾客数量grumpy[i]表示老板在第i分钟是否生气。grumpy[i] 0表示老板不生气这一分钟的顾客本来就满意grumpy[i] 1表示老板生气这一分钟的顾客本来不满意。老板有一次技巧可以让自己连续minutes分钟不生气。要求返回最多可以让多少顾客满意。复盘笔记这道题可以拆成两部分本来就满意的顾客以及使用技巧后额外挽回的顾客。如果grumpy[i] 0说明这一分钟老板本来就不生气顾客天然满意这部分一定会被计入答案。如果grumpy[i] 1说明这一分钟顾客原本不满意但如果技巧覆盖到这一分钟就可以被额外挽回。所以问题可以转化为在grumpy 1的位置中找一个长度为minutes的连续窗口使这个窗口内对应的customers总和最大。这个最大值就是技巧最多能额外挽回的顾客数。代码里可以用s [0, 0]其中s[0] 所有本来就满意的顾客数量 s[1] 当前窗口内可以被技巧挽回的顾客数量遍历时for i, (c, g) in enumerate(zip(customers, grumpy)):表示同时遍历customers和grumpy其中i是当前下标c是当前分钟顾客数g是当前分钟老板是否生气。每次执行s[g] c如果g 0就把顾客数加到s[0]表示本来就满意如果g 1就把顾客数加到s[1]表示当前窗口内可以被挽回。当窗口长度达到minutes后用当前的s[1]更新最大可挽回人数max_s1。随后窗口左端点离开如果左端点对应的是生气状态就从s[1]中减去那一分钟的顾客数。最后答案就是s[0] max_s1也就是本来就满意的顾客 技巧最多额外挽回的顾客class Solution: def maxSatisfied( self, customers: List[int], grumpy: List[int], minutes: int ) - int: s [0,0] max_s1 0 for i, (c, g) in enumerate(zip(customers, grumpy)): s[g] c left i - minutes 1 if left 0: continue max_s1 max(max_s1, s[1]) if grumpy[left]: s[1] - customers[left] return s[0] max_s1面试时所用到的一段话解释本题的思想这道题我会先把答案拆成两部分老板不生气时本来就满意的顾客以及通过技巧额外挽回的顾客。第一部分可以直接累加第二部分需要在所有长度为minutes的连续区间中找到老板生气时对应顾客数总和最大的窗口。这个窗口表示技巧使用在哪段时间最划算。最后用基础满意人数加上最大可挽回人数就是最终答案。3679.使库存平衡的最少丢弃次数题目描述给你两个整数w和m以及一个整数数组arrivals其中arrivals[i]表示第i天到达的物品类型天数从1 开始编号。物品的管理遵循以下规则每个到达的物品可以被保留或丢弃物品只能在到达当天被丢弃。对于每一天i考虑天数范围为[max(1, i - w 1), i]也就是直到第i天为止最近的w天对于任何这样的时间窗口在被保留的到达物品中每种类型最多只能出现m次。如果在第i天保留该到达物品会导致其类型在该窗口中出现次数超过m次那么该物品必须被丢弃。返回为满足每个w天的窗口中每种类型最多出现m次最少需要丢弃的物品数量。复盘笔记这道题的核心是滑动窗口加计数表。我们需要维护最近w个位置中每种事件出现了几次。如果当前事件x已经在窗口中出现了m次那么这次到达就不能再保留需要丢弃否则就把它加入窗口计数。代码里cnt [0] * (max(arrivals) 1)表示创建一个计数数组。数组下标就是事件编号cnt[x]表示事件x当前在窗口中出现了几次。之所以要开到max(arrivals) 1是因为如果最大编号是5我们需要能访问cnt[5]而数组下标从0开始所以长度必须至少是6。如果当前事件要被丢弃代码使用arrivals[i] 0后面就是标准的滑窗思路了。class Solution: def minArrivalsToDiscard(self, arrivals: List[int], w: int, m: int) - int: cnt [0]*(max(arrivals)1) ans 0 for i,x in enumerate(arrivals): if cnt[x]m: arrivals[i]0 ans1 else: cnt[x]1 left i1-w if left0: continue cnt[arrivals[left]] - 1 return ans面试时所用到的一段话解释本题的思想这道题我会用滑动窗口维护最近w个未丢弃事件的出现次数。对于当前到达的事件x如果窗口中x的数量已经等于m说明再保留它会超出限制所以丢弃否则加入计数。每轮结束时如果窗口长度已经达到w就把左端点移出窗口。这样可以保证计数表始终表示当前有效窗口内每种事件的出现次数。整体复盘总结今天这两道题都还是滑动窗口思想但维护的信息不一样。1052维护窗口内可以被技巧挽回的顾客数 到达事件丢弃维护窗口内每种事件出现次数它们的共同点是窗口都有一个固定长度每次遍历时都经历“右端点进入窗口”和“左端点离开窗口”。滑动窗口题可以先问自己三个问题1. 窗口代表什么 2. 窗口中需要维护什么信息 3. 什么时候更新答案什么时候移出左端点今天的收获是滑动窗口不只是维护一个和也可以维护计数数组、哈希表甚至把答案拆成“固定贡献 窗口额外贡献”。只要能明确窗口内的信息怎么随着右进左出而更新就可以把问题压到线性时间。