代码如诗

2940. 找到 Alice 和 Bob 可以相遇的建筑

给你一个下标从 0 开始的正整数数组 heights ，其中 heights[i] 表示第 i 栋建筑的高度。

如果一个人在建筑 i ，且存在 i < j 的建筑 j 满足 heights[i] < heights[j] ，那么这个人可以移动到建筑 j 。

给你另外一个数组 queries ，其中 queries[i] = [ai, bi] 。第 i 个查询中，Alice 在建筑 ai ，Bob 在建筑 bi 。

请你能返回一个数组 ans ，其中 ans[i] 是第 i 个查询中，Alice 和 Bob 可以相遇的 最左边的建筑 。如果对于查询 i ，Alice 和 Bob 不能相遇，令 ans[i] 为 -1 。

示例 1：

```txt

输入：heights = [6,4,8,5,2,7], queries = [[0,1],[0,3],[2,4],[3,4],[2,2]]

输出：[2,5,-1,5,2]

解释：第一个查询中，Alice 和 Bob 可以移动到建筑 2 ，因为 heights[0] < heights[2] 且 heights[1] < heights[2] 。

第二个查询中，Alice 和 Bob 可以移动到建筑 5 ，因为 heights[0] < heights[5] 且 heights[3] < heights[5] 。

第三个查询中，Alice 无法与 Bob 相遇，因为 Alice 不能移动到任何其他建筑。

第四个查询中，Alice 和 Bob 可以移动到建筑 5 ，因为 heights[3] < heights[5] 且 heights[4] < heights[5] 。

第五个查询中，Alice 和 Bob 已经在同一栋建筑中。

对于 ans[i] != -1 ，ans[i] 是 Alice 和 Bob 可以相遇的建筑中最左边建筑的下标。

对于 ans[i] == -1 ，不存在 Alice 和 Bob 可以相遇的建筑。

```

示例 2：

```txt

输入：heights = [5,3,8,2,6,1,4,6], queries = [[0,7],[3,5],[5,2],[3,0],[1,6]]

输出：[7,6,-1,4,6]

解释：第一个查询中，Alice 可以直接移动到 Bob 的建筑，因为 heights[0] < heights[7] 。

第二个查询中，Alice 和 Bob 可以移动到建筑 6 ，因为 heights[3] < heights[6] 且 heights[5] < heights[6] 。

第三个查询中，Alice 无法与 Bob 相遇，因为 Bob 不能移动到任何其他建筑。

第四个查询中，Alice 和 Bob 可以移动到建筑 4 ，因为 heights[3] < heights[4] 且 heights[0] < heights[4] 。

第五个查询中，Alice 可以直接移动到 Bob 的建筑，因为 heights[1] < heights[6] 。

对于 ans[i] != -1 ，ans[i] 是 Alice 和 Bob 可以相遇的建筑中最左边建筑的下标。

对于 ans[i] == -1 ，不存在 Alice 和 Bob 可以相遇的建筑。

```

提示：

• 1 <= heights.length <= 5 * 10^4

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

• 1 <= queries.length <= 5 * 10^4

• queries[i] = [ai, bi]

• 0 <= ai, bi <= heights.length - 1

2736. 最大和查询

给你两个长度为 n 、下标从 0 开始的整数数组 nums1 和 nums2 ，另给你一个下标从 1 开始的二维数组 queries ，其中 queries[i] = [xi, yi] 。

对于第 i 个查询，在所有满足 nums1[j] >= xi 且 nums2[j] >= yi 的下标 j (0 <= j < n) 中，找出 nums1[j] + nums2[j] 的 最大值 ，如果不存在满足条件的 j 则返回 -1 。

返回数组 answer ，其中 answer[i] 是第 i 个查询的答案。

示例 1：

```txt

输入：nums1 = [4,3,1,2], nums2 = [2,4,9,5], queries = [[4,1],[1,3],[2,5]]

输出：[6,10,7]

解释：

对于第 1 个查询：xi = 4 且 yi = 1 ，可以选择下标 j = 0 ，此时 nums1[j] >= 4 且 nums2[j] >= 1 。nums1[j] + nums2[j] 等于 6 ，可以证明 6 是可以获得的最大值。

对于第 2 个查询：xi = 1 且 yi = 3 ，可以选择下标 j = 2 ，此时 nums1[j] >= 1 且 nums2[j] >= 3 。nums1[j] + nums2[j] 等于 10 ，可以证明 10 是可以获得的最大值。

对于第 3 个查询：xi = 2 且 yi = 5 ，可以选择下标 j = 3 ，此时 nums1[j] >= 2 且 nums2[j] >= 5 。nums1[j] + nums2[j] 等于 7 ，可以证明 7 是可以获得的最大值。

因此，我们返回 [6,10,7] 。

```

示例 2：

```txt

输入：nums1 = [3,2,5], nums2 = [2,3,4], queries = [[4,4],[3,2],[1,1]]

输出：[9,9,9]

解释：对于这个示例，我们可以选择下标 j = 2 ，该下标可以满足每个查询的限制。

```

示例 3：

```txt

输入：nums1 = [2,1], nums2 = [2,3], queries = [[3,3]]

输出：[-1]

解释：示例中的查询 xi = 3 且 yi = 3 。对于每个下标 j ，都只满足 nums1[j] < xi 或者 nums2[j] < yi 。因此，不存在答案。

```

提示：

• nums1.length == nums2.length 

• n == nums1.length 

• 1 <= n <= 10^5

• 1 <= nums1[i], nums2[i] <= 10^9 

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

• queries[i].length == 2

• xi == queries[i][1]

• yi == queries[i][2]

• 1 <= xi, yi <= 10^9

753. 破解保险箱

有一个需要密码才能打开的保险箱。密码是 n 位数, 密码的每一位是 k 位序列 0, 1, ..., k-1 中的一个 。

你可以随意输入密码，保险箱会自动记住最后 n 位输入，如果匹配，则能够打开保险箱。

举个例子，假设密码是 "345"，你可以输入 "012345" 来打开它，只是你输入了 6 个字符.

请返回一个能打开保险箱的最短字符串。

示例1:

```txt

输入: n = 1, k = 2

输出: "01"

说明: "10"也可以打开保险箱。

```

示例2:

```txt

输入: n = 2, k = 2

输出: "00110"

说明: "01100", "10011", "11001" 也能打开保险箱。

```

提示：

1. n 的范围是 [1, 4]。

2. k 的范围是 [1, 10]。

3. k^n 最大可能为 4096。

332. 重新安排行程

给你一份航线列表 tickets ，其中 tickets[i] = [fromi, toi] 表示飞机出发和降落的机场地点。请你对该行程进行重新规划排序。

所有这些机票都属于一个从 JFK（肯尼迪国际机场）出发的先生，所以该行程必须从 JFK 开始。如果存在多种有效的行程，请你按字典排序返回最小的行程组合。

• 例如，行程 ["JFK", "LGA"] 与 ["JFK", "LGB"] 相比就更小，排序更靠前。

假定所有机票至少存在一种合理的行程。且所有的机票 必须都用一次 且 只能用一次。

示例 1：

```txt

输入：tickets = [["MUC","LHR"],["JFK","MUC"],["SFO","SJC"],["LHR","SFO"]]

输出：["JFK","MUC","LHR","SFO","SJC"]

```

示例 2：

```txt

输入：tickets = [["JFK","SFO"],["JFK","ATL"],["SFO","ATL"],["ATL","JFK"],["ATL","SFO"]]

输出：["JFK","ATL","JFK","SFO","ATL","SFO"]

解释：另一种有效的行程是 ["JFK","SFO","ATL","JFK","ATL","SFO"] ，但是它字典排序更大更靠后。

```

提示：

• 1 <= tickets.length <= 300

• tickets[i].length == 2

• fromi.length == 3

• toi.length == 3

• fromi 和 toi 由大写英文字母组成

• fromi != toi

3013. 将数组分成最小总代价的子数组 II

给你一个下标从 0 开始长度为 n 的整数数组 nums 和两个 正 整数 k 和 dist 。

一个数组的 代价 是数组中的 第一个 元素。比方说，[1,2,3] 的代价为 1 ，[3,4,1] 的代价为 3 。

你需要将 nums 分割成 k 个 连续且互不相交 的子数组，满足 第二 个子数组与第 k 个子数组中第一个元素的下标距离 不超过 dist 。换句话说，如果你将 nums 分割成子数组 nums[0..(i1 - 1)], nums[i1..(i2 - 1)], ..., nums[ik-1..(n - 1)] ，那么它需要满足 ik-1 - i1 <= dist 。

请你返回这些子数组的 最小 总代价。

示例 1：

```txt

输入：nums = [1,3,2,6,4,2], k = 3, dist = 3

输出：5

解释：将数组分割成 3 个子数组的最优方案是：[1,3] ，[2,6,4] 和 [2] 。这是一个合法分割，因为 ik-1 - i1 等于 5 - 2 = 3 ，等于 dist 。总代价为 nums[0] + nums[2] + nums[5] ，也就是 1 + 2 + 2 = 5 。

5 是分割成 3 个子数组的最小总代价。

```

示例 2：

```txt

输入：nums = [10,1,2,2,2,1], k = 4, dist = 3

输出：15

解释：将数组分割成 4 个子数组的最优方案是：[10] ，[1] ，[2] 和 [2,2,1] 。这是一个合法分割，因为 ik-1 - i1 等于 3 - 1 = 2 ，小于 dist 。总代价为 nums[0] + nums[1] + nums[2] + nums[3] ，也就是 10 + 1 + 2 + 2 = 15 。

分割 [10] ，[1] ，[2,2,2] 和 [1] 不是一个合法分割，因为 ik-1 和 i1 的差为 5 - 1 = 4 ，大于 dist 。

15 是分割成 4 个子数组的最小总代价。

```

示例 3：

```txt

输入：nums = [10,8,18,9], k = 3, dist = 1

输出：36

解释：将数组分割成 4 个子数组的最优方案是：[10] ，[8] 和 [18,9] 。这是一个合法分割，因为 ik-1 - i1 等于 2 - 1 = 1 ，等于 dist 。总代价为 nums[0] + nums[1] + nums[2] ，也就是 10 + 8 + 18 = 36 。

分割 [10] ，[8,18] 和 [9] 不是一个合法分割，因为 ik-1 和 i1 的差为 3 - 1 = 2 ，大于 dist 。

36 是分割成 3 个子数组的最小总代价。

```

提示：

• 3 <= n <= 10^5

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

• 3 <= k <= n

• k - 2 <= dist <= n - 2

1040. 移动石子直到连续 II

在一个长度 无限 的数轴上，第 i 颗石子的位置为 stones[i]。如果一颗石子的位置最小/最大，那么该石子被称作 端点石子 。

每个回合，你可以将一颗端点石子拿起并移动到一个未占用的位置，使得该石子不再是一颗端点石子。

值得注意的是，如果石子像 stones = [1,2,5] 这样，你将 无法 移动位于位置 5 的端点石子，因为无论将它移动到任何位置（例如 0 或 3），该石子都仍然会是端点石子。

当你无法进行任何移动时，即，这些石子的位置连续时，游戏结束。

要使游戏结束，你可以执行的最小和最大移动次数分别是多少？ 以长度为 2 的数组形式返回答案：answer = [minimum_moves, maximum_moves] 。

示例 1：

```txt

输入：[7,4,9]

输出：[1,2]

解释：

我们可以移动一次，4 -> 8，游戏结束。

或者，我们可以移动两次 9 -> 5，4 -> 6，游戏结束。

```

示例 2：

```txt

输入：[6,5,4,3,10]

输出：[2,3]

解释：

我们可以移动 3 -> 8，接着是 10 -> 7，游戏结束。

或者，我们可以移动 3 -> 7, 4 -> 8, 5 -> 9，游戏结束。

注意，我们无法进行 10 -> 2 这样的移动来结束游戏，因为这是不合要求的移动。

```

示例 3：

```txt

输入：[100,101,104,102,103]

输出：[0,0]

```

提示：

• 3 <= stones.length <= 10^4

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

• stones[i] 的值各不相同。

6293. 统计好子数组的数目

给你一个整数数组 nums 和一个整数 k ，请你返回 nums 中 好 子数组的数目。

一个子数组 arr 如果有 至少 k 对下标 (i, j) 满足 i < j 且 arr[i] == arr[j] ，那么称它是一个 好 子数组。

子数组 是原数组中一段连续 非空 的元素序列。

示例 1：

```txt

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

输出：1

解释：唯一的好子数组是这个数组本身。

```

示例 2：

```txt

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

输出：4

解释：总共有 4 个不同的好子数组：

• [3,1,4,3,2,2] 有 2 对。

• [3,1,4,3,2,2,4] 有 3 对。

• [1,4,3,2,2,4] 有 2 对。

• [4,3,2,2,4] 有 2 对。

```

提示：

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

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