标签： 滑动窗口

3134.找出唯一性数组的中位数

目标

给你一个整数数组 nums 。数组 nums 的 唯一性数组 是一个按元素从小到大排序的数组，包含了 nums 的所有 非空子数组中 不同元素的个数。

换句话说，这是由所有 0 <= i <= j < nums.length 的 distinct(nums[i..j]) 组成的递增数组。

其中，distinct(nums[i..j]) 表示从下标 i 到下标 j 的子数组中不同元素的数量。

返回 nums 唯一性数组 的 中位数 。

注意，数组的 中位数 定义为有序数组的中间元素。如果有两个中间元素，则取值较小的那个。

示例 1：

输入：nums = [1,2,3]
输出：1
解释：
nums 的唯一性数组为 [distinct(nums[0..0]), distinct(nums[1..1]), distinct(nums[2..2]), distinct(nums[0..1]), distinct(nums[1..2]), distinct(nums[0..2])]，即 [1, 1, 1, 2, 2, 3] 。唯一性数组的中位数为 1 ，因此答案是 1 。

示例 2：

输入：nums = [3,4,3,4,5]
输出：2
解释：
nums 的唯一性数组为 [1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 3, 3, 3] 。唯一性数组的中位数为 2 ，因此答案是 2 。

示例 3：

输入：nums = [4,3,5,4]
输出：2
解释：
nums 的唯一性数组为 [1, 1, 1, 1, 2, 2, 2, 3, 3, 3] 。唯一性数组的中位数为 2 ，因此答案是 2 。

说明：

  • 1 <= nums.length <= 10^5
  • 1 <= nums[i] <= 10^5

思路

定义数组的唯一性数组为其所有 子数组 中不同元素个数从小到大排序，求唯一性数组的中位数。

长度为 n 的子数组的个数为 n(n+1)/2，唯一性数组的中位数下标为 n(n+1)/4 - 1 是第 (n(n+1)/2 + 1)/2 个元素。

问题的关键在于，如何快速判断数组中不同元素的个数。我们想要这样一个hash表，可以根据 start end 动态调整其中的元素。

一般来说枚举子数组使用的是双层循环，外层枚举起点，内层从起点开始枚举终点直到结尾，当然也可以外层枚举终点，内层枚举0到终点作为起点，时间复杂度为 O(n^2)。这里的问题在于如何保存区间与对应不重复元素个数的对应关系，以及如何计算不重复元素个数。本来 O(n^2) 就会超时，如果针对每个区间再循环判断，就更不行了。这里其实可以模拟变长的滑动窗口，通过修改窗口中加入与移除元素在map中对应的计数，如果计数为0则删除，这样map里的元素个数即为当前窗口内不重复元素个数。但是并没有保存这个状态（区间对应的不同元素个数）。我们可以将 start, end 压缩到一个long型数字中，倒是也可以记录。假如我们有了这个对应关系，我们还需要将它排序然后取中位数。

看了题解使用的是二分+滑动窗口，确实比较绕，我也没有仔细想清楚，这里面有几个关键点：

  • 唯一性数组中元素的取值范围是 1 ~ n，元素递增的步长为1，如果某个子数组比之前的子数组多了2个不同的元素，那么总是可以去掉其中一个使得子数组仅多1个不同元素。
  • 思考 唯一性元素的个数 小于等于 m 的子数组有多少个？找到唯一性元素个数第一次覆盖 (n(n+1)/2 + 1)/2 的 m 就是要找的答案。
  • 假设我们已经知道 m 对应的 cnt，只需要找到第一个大于等于 (n(n+1)/2 + 1)/2 的cnt即可，可以使用二分查找。
  • 问题转化为 计算唯一性元素的个数 小于等于 m 的子数组个数。使用滑动窗口。

而这里需要计算的是子数组中不同元素的个数，

// todo

代码

性能

3086.拾起K个1需要的最少行动次数

目标

给你一个下标从 0 开始的二进制数组 nums，其长度为 n ；另给你一个 正整数 k 以及一个 非负整数 maxChanges 。

Alice 在玩一个游戏，游戏的目标是让 Alice 使用 最少 数量的 行动 次数从 nums 中拾起 k 个 1 。游戏开始时，Alice 可以选择数组 [0, n - 1] 范围内的任何索引 aliceIndex 站立。如果 nums[aliceIndex] == 1 ，Alice 会拾起一个 1 ，并且 nums[aliceIndex] 变成0（这 不算 作一次行动）。之后，Alice 可以执行 任意数量 的 行动（包括零次），在每次行动中 Alice 必须 恰好 执行以下动作之一：

  • 选择任意一个下标 j != aliceIndex 且满足 nums[j] == 0 ，然后将 nums[j] 设置为 1 。这个动作最多可以执行 maxChanges 次。
  • 选择任意两个相邻的下标 x 和 y（|x - y| == 1）且满足 nums[x] == 1, nums[y] == 0 ，然后交换它们的值（将 nums[y] = 1 和 nums[x] = 0）。如果 y == aliceIndex，在这次行动后 Alice 拾起一个 1 ，并且 nums[y] 变成 0 。

返回 Alice 拾起 恰好 k 个 1 所需的 最少 行动次数。

示例 1：

输入：nums = [1,1,0,0,0,1,1,0,0,1], k = 3, maxChanges = 1
输出：3
解释：如果游戏开始时 Alice 在 aliceIndex == 1 的位置上，按照以下步骤执行每个动作，他可以利用 3 次行动拾取 3 个 1 ：

游戏开始时 Alice 拾取了一个 1 ，nums[1] 变成了 0。此时 nums 变为 [1,0,0,0,0,1,1,0,0,1] 。
选择 j == 2 并执行第一种类型的动作。nums 变为 [1,0,1,0,0,1,1,0,0,1]
选择 x == 2 和 y == 1 ，并执行第二种类型的动作。nums 变为 [1,1,0,0,0,1,1,0,0,1] 。由于 y == aliceIndex，Alice 拾取了一个 1 ，nums 变为  [1,0,0,0,0,1,1,0,0,1] 。
选择 x == 0 和 y == 1 ，并执行第二种类型的动作。nums 变为 [0,1,0,0,0,1,1,0,0,1] 。由于 y == aliceIndex，Alice 拾取了一个 1 ，nums 变为  [0,0,0,0,0,1,1,0,0,1] 。
请注意，Alice 也可能执行其他的 3 次行动序列达成拾取 3 个 1 。

示例 2：

输入：nums = [0,0,0,0], k = 2, maxChanges = 3
输出：4
解释：如果游戏开始时 Alice 在 aliceIndex == 0 的位置上，按照以下步骤执行每个动作，他可以利用 4 次行动拾取 2 个 1 ：

选择 j == 1 并执行第一种类型的动作。nums 变为 [0,1,0,0] 。
选择 x == 1 和 y == 0 ，并执行第二种类型的动作。nums 变为 [1,0,0,0] 。由于 y == aliceIndex，Alice 拾起了一个 1 ，nums 变为 [0,0,0,0] 。
再次选择 j == 1 并执行第一种类型的动作。nums 变为 [0,1,0,0] 。
再次选择 x == 1 和 y == 0 ，并执行第二种类型的动作。nums 变为 [1,0,0,0] 。由于y == aliceIndex，Alice 拾起了一个 1 ，nums 变为 [0,0,0,0] 。

说明：

  • 2 <= n <= 10^5
  • 0 <= nums[i] <= 1
  • 1 <= k <= 10^5
  • 0 <= maxChanges <= 10^5
  • maxChanges + sum(nums) >= k

思路

有一个二进制（元素不是0就是1）数组nums，选择一个固定的位置aliceIndex，如果该位置元素值为1，则可以拾起并将元素置0。接下来可以采取行动：

  1. 任选一个不等于aliceIndex且值为0的元素置1
  2. 将任意相邻且元素值不等的元素交换，如果其中一个位置是aliceIndex，且交换后的值为1，则可以拾起这个1并将元素置0

问恰好拾起k个1所需最小行动次数。

很明显行动1要选与aliceIndex相邻的，这样才可以用行动2将1拾起。

我们首先面对的问题是aliceIndex怎么选，要拾取1就需要将1都通过行动2移动到aliceIndex周围，如果拾取一个1的行动次数大于2的话就需要考虑使用行动1直接在aliceIndex周围设置1再拾取。

// todo

代码

性能

2831.找出最长等值子数组

目标

给你一个下标从 0 开始的整数数组 nums 和一个整数 k 。

如果子数组中所有元素都相等，则认为子数组是一个 等值子数组 。注意，空数组是 等值子数组 。

从 nums 中删除最多 k 个元素后，返回可能的最长等值子数组的长度。

子数组 是数组中一个连续且可能为空的元素序列。

示例 1：

输入：nums = [1,3,2,3,1,3], k = 3
输出：3
解释：最优的方案是删除下标 2 和下标 4 的元素。
删除后，nums 等于 [1, 3, 3, 3] 。
最长等值子数组从 i = 1 开始到 j = 3 结束，长度等于 3 。
可以证明无法创建更长的等值子数组。

示例 2：

输入：nums = [1,1,2,2,1,1], k = 2
输出：4
解释：最优的方案是删除下标 2 和下标 3 的元素。 
删除后，nums 等于 [1, 1, 1, 1] 。 
数组自身就是等值子数组，长度等于 4 。 
可以证明无法创建更长的等值子数组。

说明：

  • 1 <= nums.length <= 10^5
  • 1 <= nums[i] <= nums.length
  • 0 <= k <= nums.length

思路

给定一个数组 nums 和一个正整数k，最多可以删除数组中k个元素，问数组中最长的等值子数组有多长，所谓等值子数组就是数组中的值完全相同。

直接的想法是记录每个相同元素的下标index，然后计算它们之间的距离 gap，使用滑动窗口来计算最多可以消除的 gap 数量。

注意不能优先消除序列中距离小的 gap，也就是说只能按照顺序去消除，否则可能会截断等值子数组。

刚开始使用哈希表记录相同元素的下标序列，结果提示超出内存限制，后来改用数组解决了问题。

Map在不断添加元素时可能需要进行扩容，每次扩容都需要重新分配更大的内存空间。 但我直接指定初始大小还是超出限制。

原来用了两个哈希表，indexMap 与 gapMap，后来 indexMap 改成了 List[]，gapMap 则直接在循环中计算并添加到 ArrayList 中。

注意这不是一个固定大小的窗口，如果按照固定大小的窗口去实现还是会超时。

代码

/**
 * @date 2024-05-23 0:11
 */
public class LongestEqualSubarray2831 {

    public int longestEqualSubarray_v1(List<Integer> nums, int k) {
        if (nums.size() == 0) {
            return 0;
        }
        int res = 0;
        List<Integer>[] indexMap = new List[100001];
        for (int i = 0; i < nums.size(); i++) {
            int val = nums.get(i);
            if (indexMap[val] == null) {
                indexMap[val] = new ArrayList<>();
            }
            indexMap[val].add(i);
        }
        for (List<Integer> index : indexMap) {
            if (index == null) {
                continue;
            }
            int i = 0;
            ArrayList<Integer> gaps = new ArrayList<>();
            for (int j = 1; j < index.size(); j++) {
                gaps.add(index.get(j) - index.get(i++) - 1);
            }
            int cnt = k;
            int gapNums = 0;
            int left = 0;
            int right = 0;
            while (right < gaps.size()) {
                while (cnt >= 0 && right < gaps.size()) {
                    cnt -= gaps.get(right);
                    if (cnt >= 0) {
                        right++;
                    }
                }
                gapNums = Math.max(gapNums, right - left);
                while (left < gaps.size() && cnt < 0) {
                    cnt += gaps.get(left);
                    left++;
                }
                right++;
            }

            res = Math.max(res, gapNums + 1);
        }
        return res;
    }
}

性能

又是勉强通过。//todo 性能分析与优化

1052.爱生气的书店老板

目标

有一个书店老板，他的书店开了 n 分钟。每分钟都有一些顾客进入这家商店。给定一个长度为 n 的整数数组 customers ，其中 customers[i] 是在第 i 分钟开始时进入商店的顾客数量，所有这些顾客在第 i 分钟结束后离开。

在某些时候，书店老板会生气。 如果书店老板在第 i 分钟生气，那么 grumpy[i] = 1，否则 grumpy[i] = 0。

当书店老板生气时，那一分钟的顾客就会不满意，若老板不生气则顾客是满意的。

书店老板知道一个秘密技巧，能抑制自己的情绪，可以让自己连续 minutes 分钟不生气，但却只能使用一次。

请你返回 这一天营业下来，最多有多少客户能够感到满意 。

示例 1：

输入：customers = [1,0,1,2,1,1,7,5], grumpy = [0,1,0,1,0,1,0,1], minutes = 3
输出：16
解释：书店老板在最后 3 分钟保持冷静。
感到满意的最大客户数量 = 1 + 1 + 1 + 1 + 7 + 5 = 16.

示例 2：

输入：customers = [1], grumpy = [0], minutes = 1
输出：1

说明：

  • n == customers.length == grumpy.length
  • 1 <= minutes <= n <= 2 * 10^4
  • 0 <= customers[i] <= 1000
  • grumpy[i] == 0 or 1

思路

这道题要我们求满意顾客的最大值，老板会在指定的分钟生气，生气时，当前进入的顾客就会不满意，老板可以有一次忍耐的机会在一段时间内不生气。

刚开始想复杂了，以为顾客不是马上离开，而是在i分钟后离开。其实是第i分钟结束的时候就离开了。

因此，我们只需要计算老板忍耐的时间内，原本生气影响的顾客最大值，然后再加上不生气时的顾客总数即可。

这就是一个滑动窗口问题，窗口大小为忍耐时间，记录窗口内的不满意顾客的最大值。

这里面可以优化的点是使用乘法来代替条件判断，这样可以避免分支预测失败导致额外的性能损失。

代码

/**
 * @date 2024-04-23 8:40
 */
public class MaxSatisfied1052 {

    public int maxSatisfied_v1(int[] customers, int[] grumpy, int minutes) {
        int n = customers.length;
        int total = 0;
        for (int i = 0; i < n; i++) {
            total += customers[i] * (1 - grumpy[i]);
        }
        int unsatisfiedInWindow = 0;
        for (int i = 0; i < minutes; i++) {
            unsatisfiedInWindow += customers[i] * grumpy[i];
        }
        int max = unsatisfiedInWindow;
        for (int i = minutes; i < n; i++) {
            unsatisfiedInWindow = unsatisfiedInWindow
                    - customers[i - minutes] * grumpy[i - minutes]
                    + customers[i] * grumpy[i];
            max = Math.max(max, unsatisfiedInWindow);
        }
        return total + max;
    }
}

性能

2009.使数组连续的最少操作数

目标

给你一个整数数组 nums 。每一次操作中，你可以将 nums 中 任意 一个元素替换成 任意 整数。

如果 nums 满足以下条件，那么它是 连续的 ：

  • nums 中所有元素都是 互不相同 的。
  • nums 中 最大 元素与 最小 元素的差等于 nums.length - 1 。

比方说，nums = [4, 2, 5, 3] 是 连续的 ，但是 nums = [1, 2, 3, 5, 6] 不是连续的 。

请你返回使 nums 连续 的 最少 操作次数。

示例 1：

输入：nums = [4,2,5,3]
输出：0
解释：nums 已经是连续的了。

示例 2：

输入：nums = [1,2,3,5,6]
输出：1
解释：一个可能的解是将最后一个元素变为 4 。
结果数组为 [1,2,3,5,4] ，是连续数组。

示例 3：

输入：nums = [1,10,100,1000]
输出：3
解释：一个可能的解是：
- 将第二个元素变为 2 。
- 将第三个元素变为 3 。
- 将第四个元素变为 4 。
结果数组为 [1,2,3,4] ，是连续数组。

说明：

  • 1 <= nums.length <= 10^5
  • 1 <= nums[i] <= 10^9

思路

这道题让我们求将一个数组变为连续数组所需的最小操作，所谓连续数组指数组中元素各不相同，且max - min = nums.length - 1，也就是说如果将数组从小到大排序，会得到一个公差为1的数列。

我们首先将数组排序，然后初始的数组中会有不连续的边界，也会有相等的元素。如何处理才能使数列连续，并且保证操作数最小。

我陷入了这个困境，尝试了好几个小时，试图处理各种特殊情况。比如我会先找到最大的连续子序列并且记录边界的差值，然后以它为中心分别从后面、前面获取元素来填充这个边界。并且还要计数相同元素来填充边界，这里填充的时机也会对最小的操作有影响。有时需要先填充，有时则需要最后。总之，并没有一个统一的，明确的算法来满足所有情况。

看了官网的解答，应该使用滑动窗口思想。之前一直有看到这个题型分类，没想到这就是所谓的滑动窗口。

当我遇到困难的时候会有一种执念，不愿意去看题解，想知道沿着自己的思路下去为什么不行，到最后真的有点沮丧。这样我想起了迪杰斯特拉的一个采访。

An interview with Edsger W. Dijkstra

The computer science luminary, in one of his last interviews before his death in 2002, reflects on a programmer’s life.

There’s a curious story behind your “shortest path” algorithm.

In 1956 I did two important things, I got my degree and we had the festive opening of the ARMAC(Automatic Calculator Mathematical Centre, 自动计算器数学中心).

We had to have a demonstration. Now the ARRA(Automatic Relay Calculator Amsterdam, 自动继电器计算器 阿姆斯特丹), a few years earlier, had been so unreliable that the only safe demonstration we dared to give was the generation of random numbers, but for the more reliable ARMAC I could try something more ambitious. For a demonstration for noncomputing people you have to have a problem statement that non-mathematicians can understand; they even have to understand the answer. So I designed a program that would find the shortest route between two cities in the Netherlands, using a somewhat reduced roadmap of the Netherlands, on which I had selected 64 cities (so that in the coding six bits would suffice to identify a city).

What’s the shortest way to travel from Rotterdam to Groningen? It is the algorithm for the shortest path, which I designed in about 20 minutes. One morning I was shopping in Amsterdam with my young fiancée, and tired, we sat down on the café terrace to drink a cup of coffee and I was just thinking about whether I could do this, and I then designed the algorithm for the shortest path. As I said, it was a 20-minute invention. In fact, it was published in 1959, three years later. The publication is still quite nice. One of the reasons that it is so nice was that I designed it without pencil and paper. Without pencil and paper you are almost forced to avoid all avoidable complexities.

Eventually that algorithm became, to my great amazement, one of the cornerstones of my fame. I found it in the early 1960s in a German book on management science—“Das Dijkstra’sche Verfahren” [“Dijkstra’s procedure”].

Suddenly, there was a method named after me. And it jumped again recently because it is extensively used in all travel planners. If, these days, you want to go from here to there and you have a car with a GPS and a screen, it can give you the shortest way.

1956年，迪杰斯特拉与未婚妻在阿姆斯特丹逛商场累了，坐在咖啡厅的露台上喝咖啡，他想到了一个问题"从鹿特丹到格罗宁根最短的旅行路线是什么？"，并且在20分钟内构思了最短路径算法。该算法在三年后被发表在一篇三页的论文中，题为 A note on two problems in connexion with graphs。Dijkstra 因其对开发结构化编程语言的基本贡献而获得 1972 年图灵奖，但最短路径算法仍然是他最著名的工作。

During an interview in 2001, Edsger Wybe Dijkstra revealed that he designed the algorithm in just 20 minutes while shopping in Amsterdam with his fiancée in 1956.

He was inspired by the question, "What's the shortest way to travel from Rotterdam to Groningen?"

He designed it without pencil and paper. He even mentioned that the advantage of designing without pencil and paper is that you are almost forced to avoid all avoidable complexities.

The algorithm was published three years later in a three-page article titled "A note on two problems in connexion with graphs".

https://twitter.com/LinuxHandbook/status/1754392486657798198

也许这就是天赋吧。我只是个普通人，不可能解决所有问题，没有什么可沮丧的。要努力站在巨人的肩膀上，知识并不是免费的，需要投入时间。所以没有必要死磕一个问题，快速高效的爬上去，然后当面对新的未知的问题时，再花费精力研究才对。

思考的意义可能就是让自己对困难、问题有了更深的体会，看解答要弄明白问题是如何解决的。

就以这个题为例，困难点在于如何使操作最小。虽然知道长度是固定的，但是并没有意识到如何遍历所有可能的操作方法并取其最小。陷入了具体的、面向过程的、针对案例而设计的算法之中。当我先入为主的认为，应该以最大连续子数组为中心不变，从两端借数填充这个错误的指导思想进行实现时，就注定得不到正确答案。

之所以开始会认为应该保持最大的连续子数组不变，是因为观察了几个测试案例，想当然的认为，既然最后要变成连续数组，那么保持最大的不变，操作数会最小，但其实并非如此。并且，先从后面填还是前面也是没有道理的，都是根据具体的测试案例写的。

也许其它时间，灵光一闪也会想到滑动窗口算法也说不定。如果之前接触过这个概念，那这个题还是挺简单的。

代码

// todo: 过几天自己实现一遍

性能

// todo