标签： todo

目标

你有 n 个机器人，给你两个下标从 0 开始的整数数组 chargeTimes 和 runningCosts ，两者长度都为 n 。第 i 个机器人充电时间为 chargeTimes[i] 单位时间，花费 runningCosts[i] 单位时间运行。再给你一个整数 budget 。

运行 k 个机器人 总开销 是 max(chargeTimes) + k * sum(runningCosts) ，其中 max(chargeTimes) 是这 k 个机器人中最大充电时间，sum(runningCosts) 是这 k 个机器人的运行时间之和。

请你返回在 不超过 budget 的前提下，你 最多 可以 连续 运行的机器人数目为多少。

示例 1：

输入：chargeTimes = [3,6,1,3,4], runningCosts = [2,1,3,4,5], budget = 25
输出：3
解释：
可以在 budget 以内运行所有单个机器人或者连续运行 2 个机器人。
选择前 3 个机器人，可以得到答案最大值 3 。总开销是 max(3,6,1) + 3 * sum(2,1,3) = 6 + 3 * 6 = 24 ，小于 25 。
可以看出无法在 budget 以内连续运行超过 3 个机器人，所以我们返回 3 。

示例 2：

输入：chargeTimes = [11,12,19], runningCosts = [10,8,7], budget = 19
输出：0
解释：即使运行任何一个单个机器人，还是会超出 budget，所以我们返回 0 。

说明：

• chargeTimes.length == runningCosts.length == n
• 1 <= n <= 5 * 10^4
• 1 <= chargeTimes[i], runningCosts[i] <= 10^5
• 1 <= budget <= 10^15

思路

选择连续的 k 个机器人，使开销不超过预算 budget。其中机器人的开销等于其中 所选机器人的最长的充电时间 + k * 所选k个机器人花费之和。

直接的想法是二分查找 k，然后使用滑动窗口记录最小的开销 min，如果 min < budget 增大 k，否则减小 k。时间复杂度为 O(nlogn)。

核心点在于滑动窗口的时候 max(chargeTimes) 如何更新。今天又解锁了新词条：单调队列。

// todo

代码

性能

目标

给你一个整数数组 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;
    }
}

性能