标签： easy

目标

给你个整数数组 arr，其中每个元素都 不相同。

请你找到所有具有最小绝对差的元素对，并且按升序的顺序返回。

每对元素对 [a,b] 如下：

• a , b 均为数组 arr 中的元素
• a < b
• b - a 等于 arr 中任意两个元素的最小绝对差

示例 1：

输入：arr = [4,2,1,3]
输出：[[1,2],[2,3],[3,4]]

示例 2：

输入：arr = [1,3,6,10,15]
输出：[[1,3]]

示例 3：

输入：arr = [3,8,-10,23,19,-4,-14,27]
输出：[[-14,-10],[19,23],[23,27]]

说明：

• 2 <= arr.length <= 10^5
• -10^6 <= arr[i] <= 10^6

思路

找到数组 arr 中元素值距离最小的元素对，按照升序返回。升序指 元素对 内部升序，结果集中元素对第一个元素升序。

将数组排序，最小距离在相邻元素中产生。

代码

/**
 * @date 2026-01-26 8:44
 */
public class MinimumAbsDifference1200 {

    public List<List<Integer>> minimumAbsDifference(int[] arr) {
        Arrays.sort(arr);
        List<List<Integer>> res = new ArrayList<>();
        int n = arr.length;
        int diff = Integer.MAX_VALUE;
        for (int i = 0; i < n - 1; i++) {
            diff = Math.min(diff, arr[i + 1] - arr[i]);
        }
        for (int i = 0; i < n - 1; i++) {
            if (arr[i + 1] - arr[i] == diff) {
                List<Integer> tmp = new ArrayList<>();
                tmp.add(arr[i]);
                tmp.add(arr[i + 1]);
                res.add(tmp);
            }
        }
        return res;
    }
}

性能

目标

给你一个 下标从 0 开始 的整数数组 nums ，其中 nums[i] 表示第 i 名学生的分数。另给你一个整数 k 。

从数组中选出任意 k 名学生的分数，使这 k 个分数间 最高分 和 最低分 的 差值 达到 最小化 。

返回可能的 最小差值 。

示例 1：

输入：nums = [90], k = 1
输出：0
解释：选出 1 名学生的分数，仅有 1 种方法：
- [90] 最高分和最低分之间的差值是 90 - 90 = 0
可能的最小差值是 0

示例 2：

输入：nums = [9,4,1,7], k = 2
输出：2
解释：选出 2 名学生的分数，有 6 种方法：
- [9,4,1,7] 最高分和最低分之间的差值是 9 - 4 = 5
- [9,4,1,7] 最高分和最低分之间的差值是 9 - 1 = 8
- [9,4,1,7] 最高分和最低分之间的差值是 9 - 7 = 2
- [9,4,1,7] 最高分和最低分之间的差值是 4 - 1 = 3
- [9,4,1,7] 最高分和最低分之间的差值是 7 - 4 = 3
- [9,4,1,7] 最高分和最低分之间的差值是 7 - 1 = 6
可能的最小差值是 2

说明：

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

思路

从 nums 中选择 k 个元素，求这 k 个元素中最大值与最小值的差的最小值。

要使差值最小，应该尽量缩小所选元素之间的距离。排序，使用定长滑动窗口，窗口内最大值与最小值的差即为 nums[r] - nums[l]。

代码

/**
 * @date 2026-01-26 9:59
 */
public class MinimumDifference1984 {

    public int minimumDifference(int[] nums, int k) {
        int res = Integer.MAX_VALUE;
        Arrays.sort(nums);
        int l = 0;
        int n = nums.length;
        for (int r = k - 1; r < n; r++) {
            res = Math.min(res, nums[r] - nums[l++]);
        }
        return res;
    }
}

性能

目标

给你一个数组 nums，你可以执行以下操作任意次数：

• 选择 相邻 元素对中 和最小 的一对。如果存在多个这样的对，选择最左边的一个。
• 用它们的和替换这对元素。

返回将数组变为 非递减 所需的 最小操作次数 。

如果一个数组中每个元素都大于或等于它前一个元素（如果存在的话），则称该数组为非递减。

示例 1：

输入： nums = [5,2,3,1]
输出： 2
解释：
元素对 (3,1) 的和最小，为 4。替换后 nums = [5,2,4]。
元素对 (2,4) 的和为 6。替换后 nums = [5,6]。
数组 nums 在两次操作后变为非递减。

示例 2：

输入： nums = [1,2,2]
输出： 0
解释：
数组 nums 已经是非递减的。

说明：

• 1 <= nums.length <= 50
• -1000 <= nums[i] <= 1000

思路

有一个数组 nums，每一次操作可以将数组中和最小的相邻元素用它们的和替换掉，求使得数组非递减所需要的最少操作次数。

暴力解法是每次遍历找到和最小的数对 并替换，直到数组非递减。可以使用 next 数组模拟链表来删除元素。

代码

/**
 * @date 2026-01-22 9:02
 */
public class MinimumPairRemoval3507 {

    public int minimumPairRemoval_v1(int[] nums) {
        int res = 0;
        boolean decrease;
        int n = nums.length;
        int[] next = new int[n];
        Arrays.setAll(next, i -> i + 1);
        do {
            decrease = false;
            int index = 0, sum = Integer.MAX_VALUE;
            for (int i = 0; next[i] < n; i = next[i]) {
                if (nums[next[i]] < nums[i]) {
                    decrease = true;
                }
                int s = nums[i] + nums[next[i]];
                if (s < sum) {
                    sum = s;
                    index = i;
                }
            }
            if (decrease) {
                nums[index] = sum;
                next[index] = next[next[index]];
                res++;
            }
        } while (decrease);
        return res;
    }

}

性能

目标

给你一个长度为 n 的质数数组 nums 。你的任务是返回一个长度为 n 的数组 ans ，对于每个下标 i ，以下 条件 均成立：

• ans[i] OR (ans[i] + 1) == nums[i]

除此以外，你需要 最小化 结果数组里每一个 ans[i] 。

如果没法找到符合 条件 的 ans[i] ，那么 ans[i] = -1 。

质数 指的是一个大于 1 的自然数，且它只有 1 和自己两个因数。

示例 1：

输入：nums = [2,3,5,7]
输出：[-1,1,4,3]
解释：
对于 i = 0 ，不存在 ans[0] 满足 ans[0] OR (ans[0] + 1) = 2 ，所以 ans[0] = -1 。
对于 i = 1 ，满足 ans[1] OR (ans[1] + 1) = 3 的最小 ans[1] 为 1 ，因为 1 OR (1 + 1) = 3 。
对于 i = 2 ，满足 ans[2] OR (ans[2] + 1) = 5 的最小 ans[2] 为 4 ，因为 4 OR (4 + 1) = 5 。
对于 i = 3 ，满足 ans[3] OR (ans[3] + 1) = 7 的最小 ans[3] 为 3 ，因为 3 OR (3 + 1) = 7 。

示例 2：

输入：nums = [11,13,31]
输出：[9,12,15]
解释：
对于 i = 0 ，满足 ans[0] OR (ans[0] + 1) = 11 的最小 ans[0] 为 9 ，因为 9 OR (9 + 1) = 11 。
对于 i = 1 ，满足 ans[1] OR (ans[1] + 1) = 13 的最小 ans[1] 为 12 ，因为 12 OR (12 + 1) = 13 。
对于 i = 2 ，满足 ans[2] OR (ans[2] + 1) = 31 的最小 ans[2] 为 15 ，因为 15 OR (15 + 1) = 31 。

说明：

• 1 <= nums.length <= 100
• 2 <= nums[i] <= 1000
• nums[i] 是一个质数。

思路

有一个长度为 n 的质数列表 nums，针对质数 nums.get(i)，找到最小的值 res[i] 满足 (res[i] | res[i] + 1) == nums.get(i)。

针对每一个质数，直接枚举所有可能的值，判断是否满足条件。

代码

/**
 * @date 2026-01-20 0:15
 */
public class MinBitwiseArray3314 {

    public int[] minBitwiseArray(List<Integer> nums) {
        int n = nums.size();
        int[] res = new int[n];
        Arrays.fill(res, -1);
        for (int i = 0; i < n; i++) {
            int num = nums.get(i);
            for (int j = 0; j < num; j++) {
                if ((j | (j + 1)) == num){
                    res[i] = j;
                    break;
                }
            }
        }
        return res;
    }
}

性能

目标

平面上有 n 个点，点的位置用整数坐标表示 points[i] = [xi, yi] 。请你计算访问所有这些点需要的 最小时间（以秒为单位）。

你需要按照下面的规则在平面上移动：

• 每一秒内，你可以：
  • 沿水平方向移动一个单位长度，或者
  • 沿竖直方向移动一个单位长度，或者
  • 跨过对角线移动 sqrt(2) 个单位长度（可以看作在一秒内向水平和竖直方向各移动一个单位长度）。
• 必须按照数组中出现的顺序来访问这些点。
• 在访问某个点时，可以经过该点后面出现的点，但经过的那些点不算作有效访问。

示例 1：

输入：points = [[1,1],[3,4],[-1,0]]
输出：7
解释：一条最佳的访问路径是： [1,1] -> [2,2] -> [3,3] -> [3,4] -> [2,3] -> [1,2] -> [0,1] -> [-1,0]   
从 [1,1] 到 [3,4] 需要 3 秒 
从 [3,4] 到 [-1,0] 需要 4 秒
一共需要 7 秒

示例 2：

输入：points = [[3,2],[-2,2]]
输出：5

说明：

• points.length == n
• 1 <= n <= 100
• points[i].length == 2
• -1000 <= points[i][0], points[i][1] <= 1000

思路

二维平面上有一些点 points，按顺序访问这些点，每一秒可以沿 x 轴、 y 轴 或者 格子的对角线移动，求访问所有点的最小时间。

优先走斜线，直到与下一个坐标点的 横坐标 或者 纵坐标 相等，然后再走直线。两点之间最短时间为 Math.max(dx, dy)，即切比雪夫距离。

代码

/**
 * @date 2026-01-12 8:50
 */
public class MinTimeToVisitAllPoints1266 {

    public int minTimeToVisitAllPoints(int[][] points) {
        int res = 0;
        for (int i = 1; i < points.length; i++) {
            int dx = Math.abs(points[i][0] - points[i - 1][0]);
            int dy = Math.abs(points[i][1] - points[i - 1][1]);
            res += Math.max(dx, dy);
        }
        return res;
    }
}

性能

目标

给你一个整数数组 nums ，该数组具有以下属性：

• nums.length == 2 * n.
• nums 包含 n + 1 个 不同的 元素
• nums 中恰有一个元素重复 n 次

找出并返回重复了 n 次的那个元素。

示例 1：

输入：nums = [1,2,3,3]
输出：3

示例 2：

输入：nums = [2,1,2,5,3,2]
输出：2

示例 3：

输入：nums = [5,1,5,2,5,3,5,4]
输出：5

说明：

• 2 <= n <= 5000
• nums.length == 2 * n
• 0 <= nums[i] <= 10^4
• nums 由 n + 1 个 不同的 元素组成，且其中一个元素恰好重复 n 次

思路

长度为 2 * n 数组 nums 有 n + 1 个不同元素，其中恰好有一个元素重复 n 次，返回该重复元素。

除了该重复元素，其余元素各不相同。

暴力做法是使用哈希表记录元素的出现次数，如果出现次数大于 1，直接返回，空间复杂度为 O(n)。

对于本题，从下标 1 开始与第一个元素比较，如果相等直接返回。否则问题变成从 2n - 1 个元素中找重复 n 次的元素，重复元素占绝对多数，可以使用摩尔投票算法。

还可以根据重复元素的最小间隔来分析：

• 假设重复元素至少隔着一个其它元素，有 n - 1 个空隙，至少有 2 * n - 1 个元素，可能。
• 假设重复元素至少隔着两个其它元素，有 n - 1 个空隙，至少有 n + 2 * (n - 1) = 3 * n - 2 个元素，当 n = 2 时，有可能，当 n > 2 时，必定存在一个重复元素的间隔小于 2，否则元素个数不够。

也就是说，可以检查当前元素与其前 1、2、3 个元素是否相等来找出该重复元素。空间复杂度为 O(1)。

以上算法的时间复杂度均为 O(n)，还有一种期望 O(1) 的算法，使用随机数，随机选取两个元素。它们两个相等的概率是 n/2n × (n - 1)/(2n - 1) = 1/2 * (1 - 1/n)/(2 - 1/n)，当 n = 2 时，p = 1/6，当 n -> ∞，p -> 1/4。期望循环次数 <= 6。

代码

/**
 * @date 2026-01-04 14:45
 */
public class RepeatedNTimes961 {

    public int repeatedNTimes_v1(int[] nums) {
        int n = nums.length;
        int candidate = 0;
        int vote = 0;
        for (int i = 1; i < n; i++) {
            if (nums[i] == nums[0]) {
                return nums[0];
            }
            if (vote == 0) {
                candidate = nums[i];
                vote = 1;
            } else if (candidate != nums[i]) {
                vote--;
            } else {
                return candidate;
            }
        }
        return candidate;
    }

    public int repeatedNTimes(int[] nums) {
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] == nums[i - 1] || (i >= 2 && nums[i] == nums[i - 2]) || (i >= 3 && nums[i] == nums[i - 3])) {
                return nums[i];
            }
        }
        return 0;
    }

}

性能

目标

给定一个表示 大整数 的整数数组 digits，其中 digits[i] 是整数的第 i 位数字。这些数字按从左到右，从最高位到最低位排列。这个大整数不包含任何前导 0。

将大整数加 1，并返回结果的数字数组。

示例 1：

输入：digits = [1,2,3]
输出：[1,2,4]
解释：输入数组表示数字 123。
加 1 后得到 123 + 1 = 124。
因此，结果应该是 [1,2,4]。

示例 2：

输入：digits = [4,3,2,1]
输出：[4,3,2,2]
解释：输入数组表示数字 4321。
加 1 后得到 4321 + 1 = 4322。
因此，结果应该是 [4,3,2,2]。

示例 3：

输入：digits = [9]
输出：[1,0]
解释：输入数组表示数字 9。
加 1 得到了 9 + 1 = 10。
因此，结果应该是 [1,0]。

说明：

• 1 <= digits.length <= 100
• 0 <= digits[i] <= 9
• digits 不包含任何前导 0。

思路

数组 digits 表示一个数字，高位在前低位在后，不含前导零，将该数字加一后返回。

由于存在进位，数组长度可能增加 1 位。仔细想想，第一位是 1 后面全是 0。

从后向前遍历，如数字不是 9，将数字加一直接返回，否则，将当前位置零，继续向前进位。如果遍历结束还没有返回，说明数组长度不够，新建数组，将第一位置 1 即可。

代码

/**
 * @date 2024-06-27 0:40
 */
public class PlusOne66 {

    public int[] plusOne(int[] digits) {
        int n = digits.length;
        for (int i = n - 1; i >= 0; i--) {
            int sum = digits[i] + 1;
            if (sum == 10) {
                digits[i] = 0;
            } else {
                digits[i] = sum;
                return digits;
            }
        }
        int[] res = new int[n + 1];
        res[0] = 1;
        return res;
    }

}

性能

目标

给你一个 m * n 的矩阵 grid，矩阵中的元素无论是按行还是按列，都以非严格递减顺序排列。 请你统计并返回 grid 中 负数 的数目。

示例 1：

输入：grid = [[4,3,2,-1],[3,2,1,-1],[1,1,-1,-2],[-1,-1,-2,-3]]
输出：8
解释：矩阵中共有 8 个负数。

示例 2：

输入：grid = [[3,2],[1,0]]
输出：0

说明：

• m == grid.length
• n == grid[i].length
• 1 <= m, n <= 100
• -100 <= grid[i][j] <= 100

进阶：你可以设计一个时间复杂度为 O(n + m) 的解决方案吗？

思路

有一个 m x n 矩阵 grid，按行按列非严格递减，统计其中的负数个数，要求时间复杂度为 O(m + n)。

暴力做法的复杂度为 O(m x n)。根据矩阵有序的性质，如果 grid[i][j] < 0，那么 grid[i + k][j] < 0，对于 i + k 行，只需继续向前判断，累加当前行的负数个数即可。

代码

/**
 * @date 2025-12-30 11:26
 */
public class CountNegatives1351 {

    public int countNegatives(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        int i = 0, j = n - 1;
        int res = 0;
        while (i < m) {
            while (j >= 0 && grid[i][j] < 0) {
                j--;
            }
            res += n - j - 1;
            i++;
        }
        return res;
    }

}

性能

目标

给你一个长度为 n 的数组 apple 和另一个长度为 m 的数组 capacity 。

一共有 n 个包裹，其中第 i 个包裹中装着 apple[i] 个苹果。同时，还有 m 个箱子，第 i 个箱子的容量为 capacity[i] 个苹果。

请你选择一些箱子来将这 n 个包裹中的苹果重新分装到箱子中，返回你需要选择的箱子的 最小 数量。

注意，同一个包裹中的苹果可以分装到不同的箱子中。

示例 1：

输入：apple = [1,3,2], capacity = [4,3,1,5,2]
输出：2
解释：使用容量为 4 和 5 的箱子。
总容量大于或等于苹果的总数，所以可以完成重新分装。

示例 2：

输入：apple = [5,5,5], capacity = [2,4,2,7]
输出：4
解释：需要使用所有箱子。

说明：

• 1 <= n == apple.length <= 50
• 1 <= m == capacity.length <= 50
• 1 <= apple[i], capacity[i] <= 50
• 输入数据保证可以将包裹中的苹果重新分装到箱子中。

思路

apple[i] 表示第 i 个包裹中苹果的数量，capacity[i] 表示第 i 个箱子的容量，现在需要将包裹中的苹果分装到箱子中，求所需箱子的最小数量。

累加所有苹果的数量，优先选择容量大的箱子装箱，记录箱子个数。

代码

/**
 * @date 2025-12-24 8:44
 */
public class MinimumBoxes3074 {

    public int minimumBoxes(int[] apple, int[] capacity) {
        int sum = 0;
        for (int num : apple) {
            sum += num;
        }
        Arrays.sort(capacity);
        int res = 0;
        for (int i = capacity.length - 1; i >= 0; i--) {
            if (sum <= 0) {
                break;
            }
            sum -= capacity[i];
            res++;
        }
        return res;
    }
}

性能

目标

给你由 n 个小写字母字符串组成的数组 strs，其中每个字符串长度相等。

这些字符串可以每个一行，排成一个网格。例如，strs = ["abc", "bce", "cae"] 可以排列为：

abc
bce
cae

你需要找出并删除 不是按字典序非严格递增排列的 列。在上面的例子（下标从 0 开始）中，列 0（'a', 'b', 'c'）和列 2（'c', 'e', 'e'）都是按字典序非严格递增排列的，而列 1（'b', 'c', 'a'）不是，所以要删除列 1 。

返回你需要删除的列数。

示例 1：

输入：strs = ["cba","daf","ghi"]
输出：1
解释：网格示意如下：
  cba
  daf
  ghi
列 0 和列 2 按升序排列，但列 1 不是，所以只需要删除列 1 。

示例 2：

输入：strs = ["a","b"]
输出：0
解释：网格示意如下：
  a
  b
只有列 0 这一列，且已经按升序排列，所以不用删除任何列。

示例 3：

输入：strs = ["zyx","wvu","tsr"]
输出：3
解释：网格示意如下：
  zyx
  wvu
  tsr
所有 3 列都是非升序排列的，所以都要删除。

说明：

• n == strs.length
• 1 <= n <= 100
• 1 <= strs[i].length <= 1000
• strs[i] 由小写英文字母组成

思路

有一个元素长度相同的字符串数组 strs，删掉其中不是非严格递增的列，返回删除的列数。

枚举每一列，判断是否非严格递增。

代码

/**
 * @date 2025-12-21 20:11
 */
public class MinDeletionSize944 {

    public int minDeletionSize(String[] strs) {
        int m = strs[0].length();
        int res = 0;
        for (int i = 0; i < m; i++) {
            char prev = 0;
            for (String str : strs) {
                char cur = str.charAt(i);
                if (cur < prev) {
                    res++;
                    break;
                }
                prev = cur;
            }
        }
        return res;
    }
}

性能