标签： hard

目标

给你一个整数数组 nums 。数组 nums 的 唯一性数组 是一个按元素从小到大排序的数组，包含了 nums 的所有 非空子数组中 不同元素的个数。

换句话说，这是由所有 0 <= i <= j < nums.length 的 distinct(nums[i..j]) 组成的递增数组。

其中，distinct(nums[i..j]) 表示从下标 i 到下标 j 的子数组中不同元素的数量。

返回 nums 唯一性数组 的 中位数 。

注意，数组的 中位数 定义为有序数组的中间元素。如果有两个中间元素，则取值较小的那个。

示例 1：

输入：nums = [1,2,3]
输出：1
解释：
nums 的唯一性数组为 [distinct(nums[0..0]), distinct(nums[1..1]), distinct(nums[2..2]), distinct(nums[0..1]), distinct(nums[1..2]), distinct(nums[0..2])]，即 [1, 1, 1, 2, 2, 3] 。唯一性数组的中位数为 1 ，因此答案是 1 。

示例 2：

输入：nums = [3,4,3,4,5]
输出：2
解释：
nums 的唯一性数组为 [1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 3, 3, 3] 。唯一性数组的中位数为 2 ，因此答案是 2 。

示例 3：

输入：nums = [4,3,5,4]
输出：2
解释：
nums 的唯一性数组为 [1, 1, 1, 1, 2, 2, 2, 3, 3, 3] 。唯一性数组的中位数为 2 ，因此答案是 2 。

说明：

• 1 <= nums.length <= 10^5
• 1 <= nums[i] <= 10^5

思路

定义数组的唯一性数组为其所有 子数组 中不同元素个数从小到大排序，求唯一性数组的中位数。

长度为 n 的子数组的个数为 n(n+1)/2，唯一性数组的中位数下标为 n(n+1)/4 - 1 是第 (n(n+1)/2 + 1)/2 个元素。

问题的关键在于，如何快速判断数组中不同元素的个数。我们想要这样一个hash表，可以根据 start end 动态调整其中的元素。

一般来说枚举子数组使用的是双层循环，外层枚举起点，内层从起点开始枚举终点直到结尾，当然也可以外层枚举终点，内层枚举0到终点作为起点，时间复杂度为 O(n^2)。这里的问题在于如何保存区间与对应不重复元素个数的对应关系，以及如何计算不重复元素个数。本来 O(n^2) 就会超时，如果针对每个区间再循环判断，就更不行了。这里其实可以模拟变长的滑动窗口，通过修改窗口中加入与移除元素在map中对应的计数，如果计数为0则删除，这样map里的元素个数即为当前窗口内不重复元素个数。但是并没有保存这个状态（区间对应的不同元素个数）。我们可以将 start, end 压缩到一个long型数字中，倒是也可以记录。假如我们有了这个对应关系，我们还需要将它排序然后取中位数。

看了题解使用的是二分+滑动窗口，确实比较绕，我也没有仔细想清楚，这里面有几个关键点：

• 唯一性数组中元素的取值范围是 1 ~ n，元素递增的步长为1，如果某个子数组比之前的子数组多了2个不同的元素，那么总是可以去掉其中一个使得子数组仅多1个不同元素。
• 思考 唯一性元素的个数 小于等于 m 的子数组有多少个？找到唯一性元素个数第一次覆盖 (n(n+1)/2 + 1)/2 的 m 就是要找的答案。
• 假设我们已经知道 m 对应的 cnt，只需要找到第一个大于等于 (n(n+1)/2 + 1)/2 的cnt即可，可以使用二分查找。
• 问题转化为 计算唯一性元素的个数 小于等于 m 的子数组个数。使用滑动窗口。

而这里需要计算的是子数组中不同元素的个数，

// todo

代码

性能

目标

给你一个下标从 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：

输入：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：

输入：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

思路

有一个数组 heights 表示建筑的高度，另有一个二维数组，其元素 queries[i] = [ai, bi] 表示 Alice 和 Bob 当前所在建筑的下标，规定可以从左向右移动到比当前建筑高的建筑，求 Alice 和 Bob 可以相遇的建筑下标，如果有多个取最左侧的那个。

这个问题的关键在于求出 [max(ai, bi), n) 范围内，高度大于等于 max(heights[ai], heights[bi]) 的建筑下标最小值。暴力求解会超时，考虑使用单调栈，记录下一个高度大于当前建筑的下标。类似于跳表，从较高的建筑出发，查找第一个下标大于等于max(ai, bi)的建筑即可。它存在的问题是如果(ai, bi)之间有极大值，后面还得遍历查找。最坏的情况下，数据依次递增，而满足条件的值在最后，这时退化为暴力求解。

碰巧过了。// todo 研究一下官网题解

代码

/**
 * @date 2024-08-10 19:56
 */
public class LeftmostBuildingQueries2940 {

    public int[] leftmostBuildingQueries_v1(int[] heights, int[][] queries) {
        int num = heights.length;
        int[] next = new int[num];
        Arrays.fill(next, -1);
        ArrayDeque<Integer> stack = new ArrayDeque<>();
        // 单调栈
        for (int i = 0; i < num; i++) {
            while (!stack.isEmpty() && heights[i] > heights[stack.peek()]) {
                next[stack.pop()] = i;
            }
            stack.push(i);
        }
        int n = queries.length;
        int[] res = new int[n];
        Arrays.fill(res, -1);
        for (int i = 0; i < n; i++) {
            int a = queries[i][0];
            int b = queries[i][1];
            if (a == b) {
                res[i] = a;
                continue;
            } else if (a < b && heights[a] < heights[b]) {
                res[i] = b;
                continue;
            } else if (a > b && heights[a] > heights[b]) {
                res[i] = a;
                continue;
            }
            int leftNext = Math.min(a, b);
            int rightNext = Math.max(a, b);
            if (next[leftNext] > rightNext || next[leftNext] == -1) {
                res[i] = next[leftNext];
                continue;
            }
            int height = Math.max(heights[a], heights[b]);
            while (next[rightNext] != -1) {
                if (heights[next[rightNext]] > height) {
                    res[i] = next[rightNext];
                    break;
                } else {
                    rightNext = next[rightNext];
                }
            }
        }
        return res;
    }
}

性能

目标

给你一个长度为 n 的整数数组 nums 和一个 正 整数 k 。

一个 子序列 的 能量 定义为子序列中 任意 两个元素的差值绝对值的 最小值 。

请你返回 nums 中长度 等于 k 的 所有 子序列的 能量和 。

由于答案可能会很大，将答案对 10^9 + 7 取余 后返回。

示例 1：

输入：nums = [1,2,3,4], k = 3
输出：4
解释：
nums 中总共有 4 个长度为 3 的子序列：[1,2,3] ，[1,3,4] ，[1,2,4] 和 [2,3,4] 。能量和为 |2 - 3| + |3 - 4| + |2 - 1| + |3 - 4| = 4 。

示例 2：

输入：nums = [2,2], k = 2
输出：0
解释：
nums 中唯一一个长度为 2 的子序列是 [2,2] 。能量和为 |2 - 2| = 0 。

示例 3：

输入：nums = [4,3,-1], k = 2
输出：10
解释：
nums 总共有 3 个长度为 2 的子序列：[4,3] ，[4,-1] 和 [3,-1] 。能量和为 |4 - 3| + |4 - (-1)| + |3 - (-1)| = 10 。

说明：

• 2 <= n == nums.length <= 50
• -10^8 <= nums[i] <= 10^8
• 2 <= k <= n

思路

定义数组子序列的能量为子序列中任意两个元素差的绝对值的最小值，求数组长度为k的子序列的能量和。

首先思考，数组 nums 长度为n的子序列有多少？根据每一个元素是否在序列中可知有 2^n种可能。n 最大为50，2^50 = 1125899906842624。那么长度为k的子序列有多少？ C(n,k) = n!/(k!(n-k)!)，当 k=2 时，有 n(n-1)/2 个子序列。

只能考虑动态规划，自底向上地求解。我们可以使用状态压缩来表示子序列，当状态发生转移的时候该如何处理呢？假设我们知道了某k-1子序列的能量，那么再增加一个元素能量会如何变化？比如子序列1,3,6,10，能量为2，再加入一个元素9，能量变为1。还是需要遍历子序列的。那么我们可以根据压缩的状态仅遍历哪些bit位为1的元素。剩下的问题就是如何遍历子序列了。

看了提示，首先要排序，这样差值最小的就两两相邻。刚开始的时候我也在想能不能排序，虽然子序列要保持相对顺序，但本题考虑的是子序列中绝对值差最小的，与顺序无关。

// todo

代码

性能