每日算法-250409

这是我今天的算法学习记录。

2187. 完成旅途的最少时间

题目描述

思路

二分查找

解题过程

为什么可以使用二分查找？
问题的关键在于寻找一个最小的时间 t，使得在时间 t 内所有公交车完成的总旅途次数 sum 大于等于 totalTrips。
我们可以观察到时间的单调性：如果时间 t 内可以完成 totalTrips 次旅途，那么任何大于 t 的时间 t' 肯定也可以完成（甚至完成更多）。反之，如果时间 t 内无法完成 totalTrips 次旅途（即 sum < totalTrips），那么任何小于 t 的时间 t'' 也肯定无法完成。

这种单调性（或称为“二段性”）是使用二分查找的前提。我们可以在一个可能的时间范围内（例如从 1 到一个足够大的上限）进行二分查找。

查找目标是什么？
我们要找的是满足 sum >= totalTrips 的最小时间 t。

二分步骤：

1. 确定查找范围 [left, right]。left 可以是 1，right 可以是一个合理的上界，例如 min(time) * totalTrips（即假设只有最快的车在跑，完成所有旅程所需的时间）。
2. 取中间时间 mid = left + (right - left) / 2。
3. 计算在 mid 时间内，所有公交车能完成的总旅途次数 sum。sum = Σ (mid / time[i]) 对所有 i 求和。
4. 比较 sum 和 totalTrips：
   • 如果 sum < totalTrips，说明 mid 时间太短，无法完成任务。真正的最短时间一定在 mid 右侧，所以更新 left = mid + 1。
   • 如果 sum >= totalTrips，说明 mid 时间可能是答案，或者可能还有更短的时间也满足条件。我们需要尝试更小的时间，所以更新 right = mid - 1。
5. 循环直到 left > right。最终的 left 就是满足条件的最小时间。

复杂度

• 时间复杂度: $O(N\log M)$
  • 其中 N 是公交车的数量 (time.length)。
  • M 是二分查找的时间范围的上界。在代码中，上界设置为 min(time) * totalTrips。每次二分查找需要 $O(N)$ 的时间来计算 sum 函数，二分查找本身需要 $O(\log M)$ 次迭代。
• 空间复杂度: $O(1)$
  • 我们只需要常数级别的额外空间。

Code

class Solution {
    public long minimumTime(int[] time, int totalTrips) {
        long left = 1, right = Integer.MAX_VALUE;
        for (int x : time) {
            right = Math.min(right, x);
        }
        right *= totalTrips;
        while (left <= right) {
            long mid = left + (right - left) / 2;
            if (sum(time, mid) < totalTrips) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return left;
    }

    private long sum(int[] arr, long k) {
        long sum = 0;
        for (int x : arr) {
            sum += (k / x);
        }
        return sum;
    }
}

34. 在排序数组中查找元素的第一个和最后一个位置（复习）

题目描述

今天是第二次写这道题，和上次相比已经理解了步骤，可以完全解决问题了。

详细题解见我之前的博文：每日算法-250405

Code

class Solution {
    public int[] searchRange(int[] nums, int target) {
        int left = check(nums, target);
        if (left == nums.length || nums[left] != target) {
            return new int[] {-1, -1};
        }
        int right = check(nums, target + 1) - 1;
        return new int[] {left, right};
    }

    private int check(int[] arr, int k) {
        int left = 0, right = arr.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (arr[mid] < k) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return left;
    }
}

2529. 正整数和负整数的最大计数（复习）

题目描述

今天是第二次写这道题，写的已经很顺手了，就不过多解释了。

详细题解见我之前的博文：每日算法-250406

Code

class Solution {
    public int maximumCount(int[] nums) {
        int neg = check(nums, 0);
        int pos = check(nums, 1);
        return Math.max(neg, (nums.length - pos));
    }

    private int check(int[] arr, int k) {
        int left = 0, right = arr.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (arr[mid] < k) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return left;
    }
}