fork()==0世界线变动

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

6359. 最小化数对的最大差值

给你一个下标从 0 开始的整数数组 nums 和一个整数 p 。请你从 nums 中找到 p 个下标对，每个下标对对应数值取差值，你需要使得这 p 个差值的 最大值 最小。同时，你需要确保每个下标在这 p 个下标对中最多出现一次。

对于一个下标对 i 和 j ，这一对的差值为 |nums[i] - nums[j]| ，其中 |x| 表示 x 的 绝对值 。

请你返回 p 个下标对对应数值 最大差值 的 最小值 。

示例 1：

```txt

输入：nums = [10,1,2,7,1,3], p = 2

输出：1

解释：第一个下标对选择 1 和 4 ，第二个下标对选择 2 和 5 。

最大差值为 max(|nums[1] - nums[4]|, |nums[2] - nums[5]|) = max(0, 1) = 1 。所以我们返回 1 。

```

示例 2：

```txt

输入：nums = [4,2,1,2], p = 1

输出：0

解释：选择下标 1 和 3 构成下标对。差值为 |2 - 2| = 0 ，这是最大差值的最小值。

```

提示：

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

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

• 0 <= p <= (nums.length)/2

1802. 有界数组中指定下标处的最大值

给你三个正整数 n、index 和 maxSum 。你需要构造一个同时满足下述所有条件的数组 nums（下标 从 0 开始 计数）：

• nums.length == n

• nums[i] 是 正整数 ，其中 0 <= i < n

• abs(nums[i] - nums[i+1]) <= 1 ，其中 0 <= i < n-1

• nums 中所有元素之和不超过 maxSum

• nums[index] 的值被 最大化

返回你所构造的数组中的 nums[index] 。

注意：abs(x) 等于 x 的前提是 x >= 0 ；否则，abs(x) 等于 -x 。

示例 1：

```txt

输入：n = 4, index = 2, maxSum = 6

输出：2

解释：数组 [1,1,2,1] 和 [1,2,2,1] 满足所有条件。不存在其他在指定下标处具有更大值的有效数组。

```

示例 2：

```txt

输入：n = 6, index = 1, maxSum = 10

输出：3

```

提示：

• 1 <= n <= maxSum <= 10^9

• 0 <= index < n