标签： 数组

目标

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

你必须从 nums 中选择 恰好 k 个非空子数组 nums[l..r]。子数组可以重叠，同一个子数组（相同的 l 和 r）可以 被选择超过一次。

子数组 nums[l..r] 的 值 定义为：max(nums[l..r]) - min(nums[l..r])。

总值 是所有被选子数组的 值 之和。

返回你能实现的 最大 可能总值。

子数组 是数组中连续的 非空 元素序列。

示例 1:

输入: nums = [1,3,2], k = 2
输出: 4
解释:
一种最优的方法是：
选择 nums[0..1] = [1, 3]。最大值为 3，最小值为 1，得到的值为 3 - 1 = 2。
选择 nums[0..2] = [1, 3, 2]。最大值仍为 3，最小值仍为 1，所以值也是 3 - 1 = 2。
将它们相加得到 2 + 2 = 4。

示例 2:

输入: nums = [4,2,5,1], k = 3
输出: 12
解释:
一种最优的方法是：
选择 nums[0..3] = [4, 2, 5, 1]。最大值为 5，最小值为 1，得到的值为 5 - 1 = 4。
选择 nums[1..3] = [2, 5, 1]。最大值为 5，最小值为 1，所以值也是 4。
选择 nums[2..3] = [5, 1]。最大值为 5，最小值为 1，所以值同样是 4。
将它们相加得到 4 + 4 + 4 = 12。

说明:

• 1 <= n == nums.length <= 5 * 10^4
• 0 <= nums[i] <= 10^9
• 1 <= k <= 10^5

思路

定义子数组的值是最大值与最小值之差。已知一个长度为 n 的非负整数数组 nums，从中选择 k 个子数组（允许重复选择），求所选子数组的最大总值（即子数组值之和）。

由于可以重复选择，都选区间 [0, n - 1]，区间范围越大，最大值越大，最小值越小，差值越大。

代码

/**
 * @date 2026-06-09 9:07
 */
public class MaxTotalValue3689 {

    public long maxTotalValue(int[] nums, int k) {
        int max = Integer.MIN_VALUE;
        int min = Integer.MAX_VALUE;
        for (int num : nums) {
            max = Math.max(max, num);
            min = Math.min(min, num);
        }
        return (long) (max - min) * k;
    }
}

性能

目标

给你一个下标从 0 开始的整数数组 nums 和一个整数 pivot 。请你将 nums 重新排列，使得以下条件均成立：

• 所有小于 pivot 的元素都出现在所有大于 pivot 的元素 之前 。
• 所有等于 pivot 的元素都出现在小于和大于 pivot 的元素 中间 。
• 小于 pivot 的元素之间和大于 pivot 的元素之间的 相对顺序 不发生改变。
  • 更正式的，考虑每一对 pi，pj ，pi 是初始时位置 i 元素的新位置，pj 是初始时位置 j 元素的新位置。如果 i < j 且两个元素 都 小于（或大于）pivot，那么 pi < pj 。

请你返回重新排列 nums 数组后的结果数组。

示例 1：

输入：nums = [9,12,5,10,14,3,10], pivot = 10
输出：[9,5,3,10,10,12,14]
解释：
元素 9 ，5 和 3 小于 pivot ，所以它们在数组的最左边。
元素 12 和 14 大于 pivot ，所以它们在数组的最右边。
小于 pivot 的元素的相对位置和大于 pivot 的元素的相对位置分别为 [9, 5, 3] 和 [12, 14] ，它们在结果数组中的相对顺序需要保留。

示例 2：

输入：nums = [-3,4,3,2], pivot = 2
输出：[-3,2,4,3]
解释：
元素 -3 小于 pivot ，所以在数组的最左边。
元素 4 和 3 大于 pivot ，所以它们在数组的最右边。
小于 pivot 的元素的相对位置和大于 pivot 的元素的相对位置分别为 [-3] 和 [4, 3] ，它们在结果数组中的相对顺序需要保留。

说明：

• 1 <= nums.length <= 10^5
• -10^6 <= nums[i] <= 10^6
• pivot 等于 nums 中的一个元素。

思路

根据给定数字 pivot 划分数组，左边的都小于 pivot，右边的都大于 pivot，中间的等于 pivot，同一边元素的相对位置不能改变。

直接使用两个列表保存 小于 和 大于 pivot 的元素，计算等于 pivot 的元素个数，按顺序回填原数组即可。

代码

/**
 * @date 2026-06-08 9:49
 */
public class PivotArray2161 {

    public int[] pivotArray(int[] nums, int pivot) {
        int n = nums.length;
        Deque<Integer> l = new ArrayDeque<>();
        Deque<Integer> r = new ArrayDeque<>();
        for (int num : nums) {
            if (num < pivot) {
                l.offer(num);
            } else if (num > pivot) {
                r.offer(num);
            }
        }
        int equal = n - l.size() - r.size();
        int i = 0;
        while (!l.isEmpty()) {
            nums[i++] = l.poll();
        }
        while (equal > 0){
            nums[i++] = pivot;
            equal--;
        }
        while (!r.isEmpty()) {
            nums[i++] = r.poll();
        }
        return nums;
    }

}

性能

目标

给你两种类别的游乐园项目：陆地游乐设施 和 水上游乐设施。

• 陆地游乐设施
  • landStartTime[i] – 第 i 个陆地游乐设施最早可以开始的时间。
  • landDuration[i] – 第 i 个陆地游乐设施持续的时间。
• 水上游乐设施
  • waterStartTime[j] – 第 j 个水上游乐设施最早可以开始的时间。
  • waterDuration[j] – 第 j 个水上游乐设施持续的时间。

一位游客必须从 每个 类别中体验 恰好一个 游乐设施，顺序 不限 。

• 游乐设施可以在其开放时间开始，或 之后任意时间 开始。
• 如果一个游乐设施在时间 t 开始，它将在时间 t + duration 结束。
• 完成一个游乐设施后，游客可以立即乘坐另一个（如果它已经开放），或者等待它开放。

返回游客完成这两个游乐设施的 最早可能时间 。

示例 1:

输入：landStartTime = [2,8], landDuration = [4,1], waterStartTime = [6], waterDuration = [3]
输出：9
解释：
方案 A（陆地游乐设施 0 → 水上游乐设施 0）：
在时间 landStartTime[0] = 2 开始陆地游乐设施 0。在 2 + landDuration[0] = 6 结束。
水上游乐设施 0 在时间 waterStartTime[0] = 6 开放。立即在时间 6 开始，在 6 + waterDuration[0] = 9 结束。
方案 B（水上游乐设施 0 → 陆地游乐设施 1）：
在时间 waterStartTime[0] = 6 开始水上游乐设施 0。在 6 + waterDuration[0] = 9 结束。
陆地游乐设施 1 在 landStartTime[1] = 8 开放。在时间 9 开始，在 9 + landDuration[1] = 10 结束。
方案 C（陆地游乐设施 1 → 水上游乐设施 0）：
在时间 landStartTime[1] = 8 开始陆地游乐设施 1。在 8 + landDuration[1] = 9 结束。
水上游乐设施 0 在 waterStartTime[0] = 6 开放。在时间 9 开始，在 9 + waterDuration[0] = 12 结束。
方案 D（水上游乐设施 0 → 陆地游乐设施 0）：
在时间 waterStartTime[0] = 6 开始水上游乐设施 0。在 6 + waterDuration[0] = 9 结束。
陆地游乐设施 0 在 landStartTime[0] = 2 开放。在时间 9 开始，在 9 + landDuration[0] = 13 结束。
方案 A 提供了最早的结束时间 9。

示例 2:

输入：landStartTime = [5], landDuration = [3], waterStartTime = [1], waterDuration = [10]
输出：14
解释：
方案 A（水上游乐设施 0 → 陆地游乐设施 0）：
在时间 waterStartTime[0] = 1 开始水上游乐设施 0。在 1 + waterDuration[0] = 11 结束。
陆地游乐设施 0 在 landStartTime[0] = 5 开放。立即在时间 11 开始，在 11 + landDuration[0] = 14 结束。
方案 B（陆地游乐设施 0 → 水上游乐设施 0）：
在时间 landStartTime[0] = 5 开始陆地游乐设施 0。在 5 + landDuration[0] = 8 结束。
水上游乐设施 0 在 waterStartTime[0] = 1 开放。立即在时间 8 开始，在 8 + waterDuration[0] = 18 结束。
方案 A 提供了最早的结束时间 14。

说明:

• 1 <= n, m <= 5 * 10^4
• landStartTime.length == landDuration.length == n
• waterStartTime.length == waterDuration.length == m
• 1 <= landStartTime[i], landDuration[i], waterStartTime[j], waterDuration[j] <= 10^5

思路

有两种游乐场项目，landStartTime[i]、landDuration[i] 分别表示陆上项目 i 的开始时间与持续时间，waterStartTime[i]、waterDuration[i] 分别表示水上项目 i 的开始时间与持续时间。游客需要分别游玩一个陆上项目和一个水上项目，返回最早的结束时间。

比 3633.最早完成陆地和水上游乐设施的时间I 数据范围更大，暴力解不可行。

要使完成时间最早，陆地与水上项目一定有一个是最早完成的 earliest，在此基础上另一个项目的最早完成时间为 Math.max(start, earliest) + duration。

代码

/**
 * @date 2026-06-04 10:28
 */
public class EarliestFinishTime3635 {

    public int earliestFinishTime(int[] landStartTime, int[] landDuration, int[] waterStartTime, int[] waterDuration) {
        int n = landStartTime.length;
        int m = waterStartTime.length;
        int landEarliest = Integer.MAX_VALUE;
        int waterEarliest = Integer.MAX_VALUE;
        for (int i = 0; i < n; i++) {
            landEarliest = Math.min(landEarliest, landStartTime[i] + landDuration[i]);
        }
        int res = Integer.MAX_VALUE;
        for (int i = 0; i < m; i++) {
            res = Math.min(res, Math.max(landEarliest, waterStartTime[i]) + waterDuration[i]);
            waterEarliest = Math.min(waterEarliest, waterStartTime[i] + waterDuration[i]);
        }
        for (int i = 0; i < n; i++) {
            res = Math.min(res, Math.max(waterEarliest, landStartTime[i]) + landDuration[i]);
        }
        return res;
    }
}

性能

目标

给你两个 正整数 数组 arr1 和 arr2 。

正整数的 前缀 是其 最左边 的一位或多位数字组成的整数。例如，123 是整数 12345 的前缀，而 234 不是 。

设若整数 c 是整数 a 和 b 的 公共前缀 ，那么 c 需要同时是 a 和 b 的前缀。例如，5655359 和 56554 有公共前缀 565 和 5655，而 1223 和 43456 没有 公共前缀。

你需要找出属于 arr1 的整数 x 和属于 arr2 的整数 y 组成的所有数对 (x, y) 之中最长的公共前缀的长度。

返回所有数对之中最长公共前缀的长度。如果它们之间不存在公共前缀，则返回 0 。

示例 1：

输入：arr1 = [1,10,100], arr2 = [1000]
输出：3
解释：存在 3 个数对 (arr1[i], arr2[j]) ：
- (1, 1000) 的最长公共前缀是 1 。
- (10, 1000) 的最长公共前缀是 10 。
- (100, 1000) 的最长公共前缀是 100 。
最长的公共前缀是 100 ，长度为 3 。

示例 2：

输入：arr1 = [1,2,3], arr2 = [4,4,4]
输出：0
解释：任何数对 (arr1[i], arr2[j]) 之中都不存在公共前缀，因此返回 0 。
请注意，同一个数组内元素之间的公共前缀不在考虑范围内。

说明：

• 1 <= arr1.length, arr2.length <= 5 * 10^4
• 1 <= arr1[i], arr2[i] <= 10^8

思路

有两个数组 arr1 和 arr2，返回所有数对 (arr1[i], arr2[j]) 中最长公共前缀的长度。

将 arr1 中每个数字的前缀都计入哈希表，同时判断 arr2 中每个元素的的前缀是否在哈希表中，取前缀的最大长度即可。

或者可以将 arr1 的每个元素都加入 字典树，枚举 arr2 的每一个元素，计算其在字典树中公共前缀的最大长度。

代码

/**
 * @date 2026-05-21 9:03
 */
public class LongestCommonPrefix3043 {

    static class Trie {
        public Trie[] children = new Trie[10];

        public void insert(int num) {
            String s = Integer.toString(num);
            Trie cur = this;
            for (int i = 0; i < s.length(); i++) {
                int d = s.charAt(i) - '0';
                if (cur.children[d] == null) {
                    cur.children[d] = new Trie();
                }
                cur = cur.children[d];
            }
        }

        public int prefixLength(int num) {
            String s = Integer.toString(num);
            Trie cur = this;
            int l = 0;
            for (int i = 0; i < s.length(); i++) {
                int d = s.charAt(i) - '0';
                if (cur.children[d] == null) {
                    break;
                }
                cur = cur.children[d];
                l++;
            }
            return l;
        }
    }

    public int longestCommonPrefix(int[] arr1, int[] arr2) {
        Trie root = new Trie();
        for (int num : arr1) {
            root.insert(num);
        }
        int res = 0;
        for (int num : arr2) {
            res = Math.max(res, root.prefixLength(num));
        }
        return res;
    }

}

性能