标签： hard

目标

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

代码

性能