fork()==0世界线变动

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

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

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

• nums 中所有元素都是 互不相同 的。

• nums 中 最大 元素与 最小 元素的差等于 nums.length - 1 。

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

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

示例 1：

```txt

输入：nums = [4,2,5,3]

输出：0

解释：nums 已经是连续的了。

```

示例 2：

```txt

输入：nums = [1,2,3,5,6]

输出：1

解释：一个可能的解是将最后一个元素变为 4 。

结果数组为 [1,2,3,5,4] ，是连续数组。

```

示例 3：

```txt

输入：nums = [1,10,100,1000]

输出：3

解释：一个可能的解是：

• 将第二个元素变为 2 。

• 将第三个元素变为 3 。

• 将第四个元素变为 4 。

结果数组为 [1,2,3,4] ，是连续数组。

```

提示：

• 1 <= nums.length <= 10^5

• 1 <= nums[i] <= 10^9

1482. 制作 m 束花所需的最少天数

给你一个整数数组 bloomDay，以及两个整数 m 和 k 。

现需要制作 m 束花。制作花束时，需要使用花园中 相邻的 k 朵花 。

花园中有 n 朵花，第 i 朵花会在 bloomDay[i] 时盛开，恰好 可以用于 一束 花中。

请你返回从花园中摘 m 束花需要等待的最少的天数。如果不能摘到 m 束花则返回 -1 。

示例 1：

```txt

输入：bloomDay = [1,10,3,10,2], m = 3, k = 1

输出：3

解释：让我们一起观察这三天的花开过程，x 表示花开，而 _ 表示花还未开。

现在需要制作 3 束花，每束只需要 1 朵。

1 天后：[x, , , , ] // 只能制作 1 束花

2 天后：[x, , , _, x] // 只能制作 2 束花

3 天后：[x, , x, , x] // 可以制作 3 束花，答案为 3

```

示例 2：

```txt

输入：bloomDay = [1,10,3,10,2], m = 3, k = 2

输出：-1

解释：要制作 3 束花，每束需要 2 朵花，也就是一共需要 6 朵花。而花园中只有 5 朵花，无法满足制作要求，返回 -1 。

```

示例 3：

```txt

输入：bloomDay = [7,7,7,7,12,7,7], m = 2, k = 3

输出：12

解释：要制作 2 束花，每束需要 3 朵。

花园在 7 天后和 12 天后的情况如下：

7 天后：[x, x, x, x, _, x, x]

可以用前 3 朵盛开的花制作第一束花。但不能使用后 3 朵盛开的花，因为它们不相邻。

12 天后：[x, x, x, x, x, x, x]

显然，我们可以用不同的方式制作两束花。

```

示例 4：

```txt

输入：bloomDay = [1000000000,1000000000], m = 1, k = 1

输出：1000000000

解释：需要等 1000000000 天才能采到花来制作花束

```

示例 5：

```txt

输入：bloomDay = [1,10,2,9,3,8,4,7,5,6], m = 4, k = 2

输出：9

```

提示：

• bloomDay.length == n

• 1 <= n <= 10^5

• 1 <= bloomDay[i] <= 10^9

• 1 <= m <= 10^6

• 1 <= k <= n

911. 在线选举

给你两个整数数组 persons 和 times 。在选举中，第 i 张票是在时刻为 times[i] 时投给候选人 persons[i] 的。

对于发生在时刻 t 的每个查询，需要找出在 t 时刻在选举中领先的候选人的编号。

在 t 时刻投出的选票也将被计入我们的查询之中。在平局的情况下，最近获得投票的候选人将会获胜。

实现 TopVotedCandidate 类：

• TopVotedCandidate(int[] persons, int[] times) 使用 persons 和 times 数组初始化对象。

• int q(int t) 根据前面描述的规则，返回在时刻 t 在选举中领先的候选人的编号。

示例：

```txt

输入：

["TopVotedCandidate", "q", "q", "q", "q", "q", "q"]

[[[0, 1, 1, 0, 0, 1, 0], [0, 5, 10, 15, 20, 25, 30]], [3], [12], [25], [15], [24], [8]]

输出：

[null, 0, 1, 1, 0, 0, 1]

解释：

TopVotedCandidate topVotedCandidate = new TopVotedCandidate([0, 1, 1, 0, 0, 1, 0], [0, 5, 10, 15, 20, 25, 30]);

topVotedCandidate.q(3); // 返回 0 ，在时刻 3 ，票数分布为 [0] ，编号为 0 的候选人领先。

topVotedCandidate.q(12); // 返回 1 ，在时刻 12 ，票数分布为 [0,1,1] ，编号为 1 的候选人领先。

topVotedCandidate.q(25); // 返回 1 ，在时刻 25 ，票数分布为 [0,1,1,0,0,1] ，编号为 1 的候选人领先。（在平局的情况下，1 是最近获得投票的候选人）。

topVotedCandidate.q(15); // 返回 0

topVotedCandidate.q(24); // 返回 0

topVotedCandidate.q(8); // 返回 1

```

提示：

• 1 <= persons.length <= 5000

• times.length == persons.length

• 0 <= persons[i] < persons.length

• 0 <= times[i] <= 10^9

• times 是一个严格递增的有序数组

• times[0] <= t <= 10^9

• 每个测试用例最多调用 10^4 次 q

1712. 将数组分成三个子数组的方案数

我们称一个分割整数数组的方案是 好的 ，当它满足：

• 数组被分成三个 非空 连续子数组，从左至右分别命名为 left ， mid ， right 。

• left 中元素和小于等于 mid 中元素和，mid 中元素和小于等于 right 中元素和。

给你一个 非负 整数数组 nums ，请你返回 好的 分割 nums 方案数目。由于答案可能会很大，请你将结果对 10^9 + 7 取余后返回。

示例 1：

```txt

输入：nums = [1,1,1]

输出：1

解释：唯一一种好的分割方案是将 nums 分成 [1] [1] [1] 。

```

示例 2：

```txt

输入：nums = [1,2,2,2,5,0]

输出：3

解释：nums 总共有 3 种好的分割方案：

[1] [2] [2,2,5,0]

[1] [2,2] [2,5,0]

[1,2] [2,2] [5,0]

```

示例 3：

```txt

输入：nums = [3,2,1]

输出：0

解释：没有好的分割方案。

```

提示：

• 3 <= nums.length <= 10^5

• 0 <= nums[i] <= 10^4

1201. 丑数 III

给你四个整数：n 、a 、b 、c ，请你设计一个算法来找出第 n 个丑数。

丑数是可以被 a 或 b 或 c 整除的 正整数 。

示例 1：

```txt

输入：n = 3, a = 2, b = 3, c = 5

输出：4

解释：丑数序列为 2, 3, 4, 5, 6, 8, 9, 10... 其中第 3 个是 4。

```

示例 2：

```txt

输入：n = 4, a = 2, b = 3, c = 4

输出：6

解释：丑数序列为 2, 3, 4, 6, 8, 9, 10, 12... 其中第 4 个是 6。

```

示例 3：

```txt

输入：n = 5, a = 2, b = 11, c = 13

输出：10

解释：丑数序列为 2, 4, 6, 8, 10, 11, 12, 13... 其中第 5 个是 10。

```

示例 4：

```txt

输入：n = 1000000000, a = 2, b = 217983653, c = 336916467

输出：1999999984

```

提示：

• 1 <= n, a, b, c <= 10^9

• 1 <= a * b * c <= 10^18

• 本题结果在 [1, 2 * 10^9] 的范围内

6346. 打家劫舍 IV

沿街有一排连续的房屋。每间房屋内都藏有一定的现金。现在有一位小偷计划从这些房屋中窃取现金。

由于相邻的房屋装有相互连通的防盗系统，所以小偷 不会窃取相邻的房屋 。

小偷的 窃取能力 定义为他在窃取过程中能从单间房屋中窃取的 最大金额 。

给你一个整数数组 nums 表示每间房屋存放的现金金额。形式上，从左起第 i 间房屋中放有 nums[i] 美元。

另给你一个整数数组 k ，表示窃贼将会窃取的 最少 房屋数。小偷总能窃取至少 k 间房屋。

返回小偷的 最小 窃取能力。

示例 1：

```txt

输入：nums = [2,3,5,9], k = 2

输出：5

解释：

小偷窃取至少 2 间房屋，共有 3 种方式：

• 窃取下标 0 和 2 处的房屋，窃取能力为 max(nums[0], nums[2]) = 5 。

• 窃取下标 0 和 3 处的房屋，窃取能力为 max(nums[0], nums[3]) = 9 。

• 窃取下标 1 和 3 处的房屋，窃取能力为 max(nums[1], nums[3]) = 9 。

因此，返回 min(5, 9, 9) = 5 。

```

示例 2：

```txt

输入：nums = [2,7,9,3,1], k = 2

输出：2

解释：共有 7 种窃取方式。窃取能力最小的情况所对应的方式是窃取下标 0 和 4 处的房屋。返回 max(nums[0], nums[4]) = 2 。

```

提示：

• 1 <= nums.length <= 10^5

• 1 <= nums[i] <= 10^9

• 1 <= k <= (nums.length + 1)/2

1739. 放置盒子

有一个立方体房间，其长度、宽度和高度都等于 n 个单位。请你在房间里放置 n 个盒子，每个盒子都是一个单位边长的立方体。放置规则如下：

• 你可以把盒子放在地板上的任何地方。

• 如果盒子 x 需要放置在盒子 y 的顶部，那么盒子 y 竖直的四个侧面都 必须 与另一个盒子或墙相邻。

给你一个整数 n ，返回接触地面的盒子的 最少 可能数量。

示例 1：

```txt

输入：n = 3

输出：3

解释：上图是 3 个盒子的摆放位置。

这些盒子放在房间的一角，对应左侧位置。

```

示例 2：

```txt

输入：n = 4

输出：3

解释：上图是 3 个盒子的摆放位置。

这些盒子放在房间的一角，对应左侧位置。

```

示例 3：

```txt

输入：n = 10

输出：6

解释：上图是 10 个盒子的摆放位置。

这些盒子放在房间的一角，对应后方位置。

```

提示：

• 1 <= n <= 10^9