Day3--滑动窗口与双指针--2461. 长度为 K 子数组中的最大和，1423. 可获得的最大点数，1052. 爱生气的书店老板

思路【我】：

1. 增加Map<元素，出现次数>和failNumber，来记录窗口中，不符合要求的元素个数，当failNumber==0，窗口符合要求。
2. 定长滑动窗口三部曲：入–更新–出。

class Solution {public long maximumSubarraySum(int[] nums, int k) {int n = nums.length;long sum = 0;long maxSum = 0;// map<元素，数量>Map<Integer, Integer> map = new HashMap<>();// 保存数量非1的元素个数。int failNumber = 0;for (int i = 0; i < n; i++) {// 右指针（i）进窗sum += nums[i];// 更新map与failNumber。如果出现次数>1，failNumber++map.merge(nums[i], 1, Integer::sum);if (map.get(nums[i]) > 1) {failNumber++;}// 没达到窗口大小，继续if (i < k - 1) {continue;}// 2，更新。要求failNumber==0，证明窗口中每个数只出现一次if (failNumber == 0 && sum > maxSum) {maxSum = sum;}// 3，左指针（i-k+1）出窗。更新map与failNumberint out = nums[i - k + 1];sum -= out;map.merge(out, -1, Integer::sum);// out这个元素，数量只会>=1，如果是0直接移走，其他情况,failNumber--if (map.get(out) == 0) {map.remove(out);} else {// 这里不能用else if(map.get(out)==1)来作判断条件！failNumber--;}}return maxSum;}
}

思路【我】：

1. 把最后k位挪到开头，如原来是123456，挪完后变成456123
2. 定长滑动窗口三部曲：入–更新–出。

class Solution {public int maxScore(int[] cardPoints, int k) {int n = cardPoints.length;// 把最后k位挪到开头，如原来是123456，挪完后变成456123int[] arr = new int[k * 2];for (int i = 0; i < k; i++) {arr[i + k] = cardPoints[i];arr[i] = cardPoints[n - k + i];}// 滑动窗口准备int sum = 0;int maxSum = 0;// 开始滑动for (int i = 0; i < k * 2; i++) {// 1，右指针入窗sum += arr[i];// 未达窗口大小，跳过if (i < k - 1) {continue;}// 2，更新if (sum > maxSum) {maxSum = sum;}// 3，左指针出窗sum -= arr[i - k + 1];}return maxSum;}
}

思路【我】：

1. 主要思路：先算原始origin，再算《调整》之后能带来的最大收益maxGap（通过滑动窗口）。结果就是origin+maxGap
2. 我题目读反了，干脆把0和1的含义调换，这样直接customers[i] * grumpy[i]就是满意的客户了。
3. 先算前k个，初始化
4. 再算k到n个，滑动窗口
   • 定长滑动窗口三部曲：入–更新–出。
   • 我这里微调一下，是“入–出–更新”。唯一不同的是，出的是左指针（i-k+1）的左边一位，也就是窗口外的第一位（i-k）

class Solution {public int maxSatisfied(int[] customers, int[] grumpy, int minutes) {int n = customers.length;int k = minutes;// 把0和1的含义调换，这样直接customers[i] * grumpy[i]就是满意的客户了for (int i = 0; i < n; i++) {if (grumpy[i] == 1) {grumpy[i] = 0;} else {grumpy[i] = 1;}}// 先算前k个，初始化int originK = 0;int after = 0;for (int i = 0; i < k; i++) {originK += customers[i] * grumpy[i];after += customers[i];}int gap = after - originK;int maxGap = 0;if (gap > maxGap) {maxGap = gap;}// 再算k到n个，滑动窗口for (int i = k; i < n; i++) {// 1,入if (grumpy[i] == 0) {gap += customers[i];}// 2，出。注意这里出的是左指针（i-k+1）的左边一位，也就是窗口外的第一位（i-k）if (grumpy[i - k] == 0) {gap -= customers[i - k];}// 3，更新if (gap > maxGap) {maxGap = gap;}}// 计算originint origin = 0;for (int i = 0; i < n; i++) {origin += customers[i] * grumpy[i];}return origin + maxGap;}
}

思路【灵艾山茶府】：

1. 找到窗口为minutes的，最多不满意顾客的区间，把他们都变成满意，就能最大化了。
2. sum0 是老板不生气的时候，满意的顾客的总和；sum1 是老板生气的时候，不满意的顾客总和
3. 定长滑动窗口三部曲：入–更新–出。
4. 原来就满意的顾客+最多不满意的顾客区间(这段时间都会被秘密技巧变成不生气),就是答案.

class Solution {public int maxSatisfied(int[] customers, int[] grumpy, int minutes) {int n = customers.length;int k = minutes;// sum0 是老板不生气的时候，满意的顾客的总和int sum0 = 0;// sum1 是老板生气的时候，不满意的顾客总和int sum1 = 0;// 找到窗口为minutes的，最多不满意顾客的区间，把他们都变成满意，就能最大化了。int maxSum1 = 0;for (int i = 0; i < n; i++) {// 1, 入根据生气状态，分别加和if (grumpy[i] == 1) {sum1 += customers[i];} else {sum0 += customers[i];}// 没达到窗口大小,跳过if (i < k - 1) {continue;}// 2,更新if (sum1 > maxSum1) {maxSum1 = sum1;}// 3,出.if (grumpy[i - k + 1] == 1) {sum1 -= customers[i - k + 1];}}// 原来就满意的顾客+最多不满意的顾客区间(这段时间都会被秘密技巧变成不生气),就是答案.return sum0 + maxSum1;}
}

这道题完完全全就是上一道题1052. 爱生气的书店老板的升级版。这道题是2025年8月17日的力扣463场周赛题。刚好两道题是同一天做的。

• 上一道题是只有两个状态，1和0，而且k里面的操作是统一的。
• 这一题有三个状态，-1，0，1.而且k里面的操作是不统一的，前k/2变为0，后k/2变为1。难度一下子就上升了很多了。

思路【我】：

1. 总体思路：定长滑动窗口。每滑动一个位置，要算左右指针位置的得失值，和中间位置的得失值（中间位置从1变0）。得失值记为gap，原始值记为origin。最终结果就是maxGap + origin。
2. 计算无《修改》时候的总额，记为origin
3. 计算前k个，使用《修改》之后的gap变化
4. 定长滑动窗口三部曲：入–更新–出。——我这里微调一下，是“入–出–更新”。唯一不同的是，出的是左指针（i-k+1）的左边一位，也就是窗口外的第一位（i-k）
   1. 入：讨论：如果i位置，原策略为-1，现在变为1，等于增加两份price；同理，如果原策略为0，现在为1，等于增加一份price
   2. 中：这个位置，因为右移了一位，从原来的策略1变成了0，所以要减去一份price
   3. 出：注意，这里不是窗口最左边的元素（i-k+1），而是窗口外的左边第一位元素，即出窗的第一位。
   4. 更新maxGap
5. 最终结果就是maxGap + origin。

class Solution {public long maxProfit(int[] prices, int[] strategy, int k) {// 思路：定长滑动窗口// 每滑动一个位置，要算左右指针位置的得失值，和中间位置的得失值（中间位置从1变0）// 结果就是maxGap + originint n = prices.length;// 计算无《修改》时候的总额，记为originlong origin = 0;for (int i = 0; i < n; i++) {origin += (long) (prices[i] * strategy[i]);}// 计算前k个，使用《修改》之后的gap变化long originK = 0;long afterK = 0;for (int i = 0; i < k; i++) {// 前面的k/2是0，所以不用累加if (i >= k / 2) {afterK += prices[i];}// 不使用《修改》情况下的总和originK += prices[i] * strategy[i];}// 前k个数使用《修改》后的gap值long gap = afterK - originK;long maxGap = 0;if (gap > maxGap) {maxGap = gap;}// 开始滑动窗口for (int i = k; i < n; i++) {// right就是i// 讨论：如果i位置，原策略为-1，现在变为1，等于增加两份price；同理，如果原策略为0，现在为1，等于增加一份priceif (strategy[i] == -1) {gap += prices[i] * 2;} else if (strategy[i] == 0) {gap += prices[i];}// 中// 这个位置，因为右移了一位，从原来的策略1变成了0，所以要减去一份priceint mid = i - k / 2;gap -= prices[mid];// 左'：注意，这里不是窗口最左边的元素（i-k+1），而是窗口外的左边第一位元素，即出窗的第一位。int left = i - k;// 如果原策略为-1，《修改》使它变成0了，现在要变回-1，是损失了一份price；// 如果原策略为1，《修改》使它变成0了，现在要变回1，是增加了一份priceif (strategy[left] == -1) {gap -= prices[left];} else if (strategy[left] == 1) {gap += prices[left];}// 更新maxGapif (gap > maxGap) {maxGap = gap;}}// 《修改》后获得的gap加上原值origin，就是结果return maxGap + origin;}
}

思路【灵艾山茶府】：

思路总体上是一样的，但是整体上看来，简洁了很多，为什么？

两点。

1. 在“入”的时候，直接用price*(1-strategy)，这样直接不用讨论strategy的三种情况了，太有灵性了，题做少了就想不到。
2. 在“出”的时候，我也是在思考，strategy原策略是-1，《修改》后变成0，如今出窗口又变回-1，是损失了一份price。但是灵艾山茶府的思维，就是直接gap += prices[i - k] * strategy[i - k];一句话搞定——不用考虑原策略的问题，现在是0，变成了1就增加，变成了-1就减少，而strategy刚好提供了符号，直接+=就好。

class Solution {public long maxProfit(int[] prices, int[] strategy, int k) {// 思路：定长滑动窗口int n = prices.length;long origin = 0;long gap = 0;long maxGap = 0;// 计算第一个窗口for (int i = 0; i < k / 2; i++) {int p = prices[i], s = strategy[i];origin += p * s;gap -= p * s;}for (int i = k / 2; i < k; i++) {int p = prices[i], s = strategy[i];origin += p * s;gap += p * (1 - s);}if (gap > maxGap) {maxGap = gap;}// 开始滑动窗口for (int i = k; i < n; i++) {int p = prices[i], s = strategy[i];origin += p * s;// 1，入gap += p * (1 - s);// 2，中间位置处理，窗口中间位置的策略，从1变0，减少一份pricegap -= prices[i - k / 2];// 3，出。这里出的不是通常的左指针（i-k+1），而是窗口左外的第一个元素（i-k）gap += prices[i - k] * strategy[i - k];// 4，更新if (gap > maxGap) {maxGap = gap;}}// 结果就是原来的值origin加上maxGapreturn origin + maxGap;}
}