代码如诗

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

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

2528. 最大化城市的最小供电站数目

给你一个下标从 0 开始长度为 n 的整数数组 stations ，其中 stations[i] 表示第 i 座城市的供电站数目。

每个供电站可以在一定 范围 内给所有城市提供电力。换句话说，如果给定的范围是 r ，在城市 i 处的供电站可以给所有满足 |i - j| <= r 且 0 <= i, j <= n - 1 的城市 j 供电。

• |x| 表示 x 的 绝对值 。比方说，|7 - 5| = 2 ，|3 - 10| = 7 。

一座城市的 电量 是所有能给它供电的供电站数目。

政府批准了可以额外建造 k 座供电站，你需要决定这些供电站分别应该建在哪里，这些供电站与已经存在的供电站有相同的供电范围。

给你两个整数 r 和 k ，如果以最优策略建造额外的发电站，返回所有城市中，最小供电站数目的最大值是多少。

这 k 座供电站可以建在多个城市。

示例 1：

```txt

输入：stations = [1,2,4,5,0], r = 1, k = 2

输出：5

解释：

最优方案之一是把 2 座供电站都建在城市 1 。

每座城市的供电站数目分别为 [1,4,4,5,0] 。

• 城市 0 的供电站数目为 1 + 4 = 5 。

• 城市 1 的供电站数目为 1 + 4 + 4 = 9 。

• 城市 2 的供电站数目为 4 + 4 + 5 = 13 。

• 城市 3 的供电站数目为 5 + 4 = 9 。

• 城市 4 的供电站数目为 5 + 0 = 5 。

供电站数目最少是 5 。

无法得到更优解，所以我们返回 5 。

```

示例 2：

```txt

输入：stations = [4,4,4,4], r = 0, k = 3

输出：4

解释：

无论如何安排，总有一座城市的供电站数目是 4 ，所以最优解是 4 。

```

提示：

• n == stations.length

• 1 <= n <= 10^5

• 0 <= stations[i] <= 10^5

• 0 <= r <= n - 1

• 0 <= k <= 10^9

1631. 最小体力消耗路径

你准备参加一场远足活动。给你一个二维 rows x columns 的地图 heights ，其中 heights[row][col] 表示格子 (row, col) 的高度。一开始你在最左上角的格子 (0, 0) ，且你希望去最右下角的格子 (rows-1, columns-1) （注意下标从 0 开始编号）。你每次可以往 上，下，左，右 四个方向之一移动，你想要找到耗费 体力 最小的一条路径。

一条路径耗费的 体力值 是路径上相邻格子之间 高度差绝对值 的 最大值 决定的。

请你返回从左上角走到右下角的最小 体力消耗值 。

示例 1：

```txt

输入：heights = [[1,2,2],[3,8,2],[5,3,5]]

输出：2

解释：路径 [1,3,5,3,5] 连续格子的差值绝对值最大为 2 。

这条路径比路径 [1,2,2,2,5] 更优，因为另一条路径差值最大值为 3 。

```

示例 2：

```txt

输入：heights = [[1,2,3],[3,8,4],[5,3,5]]

输出：1

解释：路径 [1,2,3,4,5] 的相邻格子差值绝对值最大为 1 ，比路径 [1,3,5,3,5] 更优。

```

示例 3：

```txt

输入：heights = [[1,2,1,1,1],[1,2,1,2,1],[1,2,1,2,1],[1,2,1,2,1],[1,1,1,2,1]]

输出：0

解释：上图所示路径不需要消耗任何体力。

```

提示：

• rows == heights.length

• columns == heights[i].length

• 1 <= rows, columns <= 100

• 1 <= heights[i][j] <= 10^6