fork()==0世界线变动

1825. 求出 MK 平均值

给你两个整数 m 和 k ，以及数据流形式的若干整数。你需要实现一个数据结构，计算这个数据流的 MK 平均值 。

MK 平均值 按照如下步骤计算：

1. 如果数据流中的整数少于 m 个，MK 平均值 为 -1 ，否则将数据流中最后 m 个元素拷贝到一个独立的容器中。

2. 从这个容器中删除最小的 k 个数和最大的 k 个数。

3. 计算剩余元素的平均值，并 向下取整到最近的整数 。

请你实现 MKAverage 类：

• MKAverage(int m, int k) 用一个空的数据流和两个整数 m 和 k 初始化 MKAverage 对象。

• void addElement(int num) 往数据流中插入一个新的元素 num 。

• int calculateMKAverage() 对当前的数据流计算并返回 MK 平均数 ，结果需 向下取整到最近的整数 。

示例 1：

```txt

输入：

["MKAverage", "addElement", "addElement", "calculateMKAverage", "addElement", "calculateMKAverage", "addElement", "addElement", "addElement", "calculateMKAverage"]

[[3, 1], [3], [1], [], [10], [], [5], [5], [5], []]

输出：

[null, null, null, -1, null, 3, null, null, null, 5]

解释：

MKAverage obj = new MKAverage(3, 1);

obj.addElement(3); // 当前元素为 [3]

obj.addElement(1); // 当前元素为 [3,1]

obj.calculateMKAverage(); // 返回 -1 ，因为 m = 3 ，但数据流中只有 2 个元素

obj.addElement(10); // 当前元素为 [3,1,10]

obj.calculateMKAverage(); // 最后 3 个元素为 [3,1,10]

                      // 删除最小以及最大的 1 个元素后，容器为 [3]                      // [3] 的平均值等于 3/1 = 3 ，故返回 3

obj.addElement(5); // 当前元素为 [3,1,10,5]

obj.addElement(5); // 当前元素为 [3,1,10,5,5]

obj.addElement(5); // 当前元素为 [3,1,10,5,5,5]

obj.calculateMKAverage(); // 最后 3 个元素为 [5,5,5]

                      // 删除最小以及最大的 1 个元素后，容器为 [5]                      // [5] 的平均值等于 5/1 = 5 ，故返回 5

```

提示：

• 3 <= m <= 10^5

• 1 <= k*2 < m

• 1 <= num <= 10^5

• addElement 与 calculateMKAverage 总操作次数不超过 10^5 次。

1172. 餐盘栈

我们把无限数量 ∞ 的栈排成一行，按从左到右的次序从 0 开始编号。每个栈的的最大容量 capacity 都相同。

实现一个叫「餐盘」的类 DinnerPlates：

• DinnerPlates(int capacity) - 给出栈的最大容量 capacity。

• void push(int val) - 将给出的正整数 val 推入 从左往右第一个 没有满的栈。

• int pop() - 返回 从右往左第一个 非空栈顶部的值，并将其从栈中删除；如果所有的栈都是空的，请返回 -1。

• int popAtStack(int index) - 返回编号 index 的栈顶部的值，并将其从栈中删除；如果编号 index 的栈是空的，请返回 -1。

示例：

```txt

输入：

["DinnerPlates","push","push","push","push","push","popAtStack","push","push","popAtStack","popAtStack","pop","pop","pop","pop","pop"]

[[2],[1],[2],[3],[4],[5],[0],[20],[21],[0],[2],[],[],[],[],[]]

输出：

[null,null,null,null,null,null,2,null,null,20,21,5,4,3,1,-1]

解释：

DinnerPlates D = DinnerPlates(2); // 初始化，栈最大容量 capacity = 2

D.push(1);

D.push(2);

D.push(3);

D.push(4);

D.push(5); // 栈的现状为： 2  4

1  3  5

                                ﹈ ﹈ ﹈

D.popAtStack(0); // 返回 2。栈的现状为：  4

                                      1  3  5                                      ﹈ ﹈ ﹈

D.push(20); // 栈的现状为： 20 4

1  3  5

                               ﹈ ﹈ ﹈

D.push(21); // 栈的现状为： 20 4 21

1  3  5

                               ﹈ ﹈ ﹈

D.popAtStack(0); // 返回 20。栈的现状为： 4 21

                                        1  3  5                                        ﹈ ﹈ ﹈

D.popAtStack(2); // 返回 21。栈的现状为： 4

                                        1  3  5                                        ﹈ ﹈ ﹈

D.pop() // 返回 5。栈的现状为： 4

                                        1  3                                        ﹈ ﹈

D.pop() // 返回 4。栈的现状为： 1 3

                                       ﹈ ﹈

D.pop() // 返回 3。栈的现状为： 1

                                       ﹈

D.pop() // 返回 1。现在没有栈。

D.pop() // 返回 -1。仍然没有栈。

```

提示：

• 1 <= capacity <= 20000

• 1 <= val <= 20000

• 0 <= index <= 100000

• 最多会对 push，pop，和 popAtStack 进行 200000 次调用。

1697. 检查边长度限制的路径是否存在

给你一个 n 个点组成的无向图边集 edgeList ，其中 edgeList[i] = [ui, vi, disi] 表示点 ui 和点 vi 之间有一条长度为 disi 的边。请注意，两个点之间可能有 超过一条边 。

给你一个查询数组queries ，其中 queries[j] = [pj, qj, limitj] ，你的任务是对于每个查询 queries[j] ，判断是否存在从 pj 到 qj 的路径，且这条路径上的每一条边都 严格小于 limitj 。

请你返回一个 布尔数组 answer ，其中 answer.length == queries.length ，当 queries[j] 的查询结果为 true 时， answer 第 j 个值为 true ，否则为 false 。

示例 1：

```

输入：n = 3, edgeList = [[0,1,2],[1,2,4],[2,0,8],[1,0,16]], queries = [[0,1,2],[0,2,5]]

输出：[false,true]

解释：上图为给定的输入数据。注意到 0 和 1 之间有两条重边，分别为 2 和 16 。

对于第一个查询，0 和 1 之间没有小于 2 的边，所以我们返回 false 。

对于第二个查询，有一条路径（0 -> 1 -> 2）两条边都小于 5 ，所以这个查询我们返回 true 。

```

示例 2：

```

输入：n = 5, edgeList = [[0,1,10],[1,2,5],[2,3,9],[3,4,13]], queries = [[0,4,14],[1,4,13]]

输出：[true,false]

解释：上图为给定数据。

```

提示：

• 2 <= n <= 10^5

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

• edgeList[i].length == 3

• queries[j].length == 3

• 0 <= ui, vi, pj, qj <= n - 1

• ui != vi

• pj != qj

• 1 <= disi, limitj <= 10^9

• 两个点之间可能有 多条 边。

2503. 矩阵查询可获得的最大分数

给你一个大小为 m x n 的整数矩阵 grid 和一个大小为 k 的数组 queries 。

找出一个大小为 k 的数组 answer ，且满足对于每个整数 queres[i] ，你从矩阵 左上角 单元格开始，重复以下过程：

• 如果 queries[i] 严格 大于你当前所处位置单元格，如果该单元格是第一次访问，则获得 1 分，并且你可以移动到所有 4 个方向（上、下、左、右）上任一 相邻 单元格。

• 否则，你不能获得任何分，并且结束这一过程。

在过程结束后，answer[i] 是你可以获得的最大分数。注意，对于每个查询，你可以访问同一个单元格 多次 。

返回结果数组 answer 。

示例 1：

```

输入：grid = [[1,2,3],[2,5,7],[3,5,1]], queries = [5,6,2]

输出：[5,8,1]

解释：上图展示了每个查询中访问并获得分数的单元格。

```

示例 2：

```

输入：grid = [[5,2,1],[1,1,2]], queries = [3]

输出：[0]

解释：无法获得分数，因为左上角单元格的值大于等于 3 。

```

提示：

• m == grid.length

• n == grid[i].length

• 2 <= m, n <= 1000

• 4 <= m * n <= 10^5

• k == queries.length

• 1 <= k <= 10^4

• 1 <= grid[i][j], queries[i] <= 10^6

1632. 矩阵转换后的秩

给你一个 m x n 的矩阵 matrix ，请你返回一个新的矩阵 answer ，其中 answer[row][col] 是 matrix[row][col] 的秩。

每个元素的 秩 是一个整数，表示这个元素相对于其他元素的大小关系，它按照如下规则计算：

• 秩是从 1 开始的一个整数。

• 如果两个元素 p 和 q 在 同一行 或者 同一列 ，那么：

  • 如果 p < q ，那么 rank(p) < rank(q)

  • 如果 p == q ，那么 rank(p) == rank(q)

  • 如果 p > q ，那么 rank(p) > rank(q)

• 秩 需要越 小 越好。

题目保证按照上面规则 answer 数组是唯一的。

示例 1：

```txt

输入：matrix = [[1,2],[3,4]]

输出：[[1,2],[2,3]]

解释：

matrix[0][0] 的秩为 1 ，因为它是所在行和列的最小整数。

matrix[0][1] 的秩为 2 ，因为 matrix[0][1] > matrix[0][0] 且 matrix[0][0] 的秩为 1 。

matrix[1][0] 的秩为 2 ，因为 matrix[1][0] > matrix[0][0] 且 matrix[0][0] 的秩为 1 。

matrix[1][1] 的秩为 3 ，因为 matrix[1][1] > matrix[0][1]， matrix[1][1] > matrix[1][0] 且 matrix[0][1] 和 matrix[1][0] 的秩都为 2 。

```

示例 2：

```txt

输入：matrix = [[7,7],[7,7]]

输出：[[1,1],[1,1]]

```

示例 3：

```txt

输入：matrix = [[20,-21,14],[-19,4,19],[22,-47,24],[-19,4,19]]

输出：[[4,2,3],[1,3,4],[5,1,6],[1,3,4]]

```

示例 4：

```txt

输入：matrix = [[7,3,6],[1,4,5],[9,8,2]]

输出：[[5,1,4],[1,2,3],[6,3,1]]

```

提示：

• m == matrix.length

• n == matrix[i].length

• 1 <= m, n <= 500

• -10^9 <= matrix[row][col] <= 10^9

2856. 删除数对后的最小数组长度

给你一个下标从 0 开始的 非递减 整数数组 nums 。

你可以执行以下操作任意次：

• 选择 两个 下标 i 和 j ，满足 i < j 且 nums[i] < nums[j] 。

• 将 nums 中下标在 i 和 j 处的元素删除。剩余元素按照原来的顺序组成新的数组，下标也重新从 0 开始编号。

请你返回一个整数，表示执行以上操作任意次后（可以执行 0 次），nums 数组的 最小 数组长度。

示例 1：

```txt

输入：nums = [1,3,4,9]

输出：0

解释：一开始，nums = [1, 3, 4, 9] 。

第一次操作，我们选择下标 0 和 1 ，满足 nums[0] < nums[1] <=> 1 < 3 。

删除下标 0 和 1 处的元素，nums 变成 [4, 9] 。

下一次操作，我们选择下标 0 和 1 ，满足 nums[0] < nums[1] <=> 4 < 9 。

删除下标 0 和 1 处的元素，nums 变成空数组 [] 。

所以，可以得到的最小数组长度为 0 。

```

示例 2：

```txt

输入：nums = [2,3,6,9]

输出：0

解释：一开始，nums = [2, 3, 6, 9] 。

第一次操作，我们选择下标 0 和 2 ，满足 nums[0] < nums[2] <=> 2 < 6 。

删除下标 0 和 2 处的元素，nums 变成 [3, 9] 。

下一次操作，我们选择下标 0 和 1 ，满足 nums[0] < nums[1] <=> 3 < 9 。

删除下标 0 和 1 处的元素，nums 变成空数组 [] 。

所以，可以得到的最小数组长度为 0 。

```

示例 3：

```txt

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

输出：1

解释：一开始，nums = [1, 1, 2] 。

第一次操作，我们选择下标 0 和 2 ，满足 nums[0] < nums[2] <=> 1 < 2 。

删除下标 0 和 2 处的元素，nums 变成 [1] 。

无法对数组再执行操作。

所以，可以得到的最小数组长度为 1 。

```

提示：

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

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

• nums 是 非递减 数组。

2983. 回文串重新排列查询

给你一个长度为 偶数 n ，下标从 0 开始的字符串 s 。

同时给你一个下标从 0 开始的二维整数数组 queries ，其中 queries[i] = [ai, bi, ci, di] 。

对于每个查询 i ，你需要执行以下操作：

• 将下标在范围 0 <= ai <= bi < n / 2 内的 子字符串 s[ai:bi] 中的字符重新排列。

• 将下标在范围 n / 2 <= ci <= di < n 内的 子字符串 s[ci:di] 中的字符重新排列。

对于每个查询，你的任务是判断执行操作后能否让 s 变成一个 回文串 。

每个查询与其他查询都是 独立的 。

请你返回一个下标从 0 开始的数组 answer ，如果第 i 个查询执行操作后，可以将 s 变为一个回文串，那么 answer[i] = true，否则为 false 。

• 子字符串 指的是一个字符串中一段连续的字符序列。

• s[x:y] 表示 s 中从下标 x 到 y 且两个端点 都包含 的子字符串。

示例 1：

```txt

输入：s = "abcabc", queries = [[1,1,3,5],[0,2,5,5]]

输出：[true,true]

解释：这个例子中，有 2 个查询：

第一个查询：

• a0 = 1, b0 = 1, c0 = 3, d0 = 5

• 你可以重新排列 s[1:1] => abcabc 和 s[3:5] => abcabc 。

• 为了让 s 变为回文串，s[3:5] 可以重新排列得到 => abccba 。

• 现在 s 是一个回文串。所以 answer[0] = true 。

第二个查询：

• a1 = 0, b1 = 2, c1 = 5, d1 = 5.

• 你可以重新排列 s[0:2] => abcabc 和 s[5:5] => abcabc 。

• 为了让 s 变为回文串，s[0:2] 可以重新排列得到 => cbaabc 。

• 现在 s 是一个回文串，所以 answer[1] = true 。

```

示例 2：

```txt

输入：s = "abbcdecbba", queries = [[0,2,7,9]]

输出：[false]

解释：这个示例中，只有一个查询。

a0 = 0, b0 = 2, c0 = 7, d0 = 9.

你可以重新排列 s[0:2] => abbcdecbba 和 s[7:9] => abbcdecbba 。

无法通过重新排列这些子字符串使 s 变为一个回文串，因为 s[3:6] 不是一个回文串。

所以 answer[0] = false 。

```

示例 3：

```txt

输入：s = "acbcab", queries = [[1,2,4,5]]

输出：[true]

解释：这个示例中，只有一个查询。

a0 = 1, b0 = 2, c0 = 4, d0 = 5.

你可以重新排列 s[1:2] => acbcab 和 s[4:5] => acbcab 。

为了让 s 变为回文串，s[1:2] 可以重新排列得到 => abccab 。

然后 s[4:5] 重新排列得到 abccba 。

现在 s 是一个回文串，所以 answer[0] = true 。

```

提示：

• 2 <= n == s.length <= 10^5

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

• queries[i].length == 4

• ai == queries[i][0], bi == queries[i][1]

• ci == queries[i][2], di == queries[i][3]

• 0 <= ai <= bi < n / 2

• n / 2 <= ci <= di < n

• n 是一个偶数。

• s 只包含小写英文字母。