标签： 二分查找

目标

给你一个大小为 m x n 的矩阵 mat 和一个整数阈值 threshold。

请你返回元素总和小于或等于阈值的正方形区域的最大边长；如果没有这样的正方形区域，则返回 0 。

示例 1：

输入：mat = [[1,1,3,2,4,3,2],[1,1,3,2,4,3,2],[1,1,3,2,4,3,2]], threshold = 4
输出：2
解释：总和小于或等于 4 的正方形的最大边长为 2，如图所示。

示例 2：

输入：mat = [[2,2,2,2,2],[2,2,2,2,2],[2,2,2,2,2],[2,2,2,2,2],[2,2,2,2,2]], threshold = 1
输出：0

说明：

• m == mat.length
• n == mat[i].length
• 1 <= m, n <= 300
• 0 <= mat[i][j] <= 10^4
• 0 <= threshold <= 10^5

思路

有一个 m x n 矩阵，返回其中元素和不超过 threshold 的正方形的最大边长。

使用二维前缀和计算面积，枚举右下顶点与边长，边长从已知的最大值开始枚举，超出 threshold 就退出循环，时间复杂度为 O(mn + min(m, n))。

代码

/**
 * @date 2026-01-19 9:46
 */
public class MaxSideLength1292 {

    public int maxSideLength_v1(int[][] mat, int threshold) {
        int m = mat.length;
        int n = mat[0].length;
        int[][] prefix = new int[m + 1][n + 1];
        int res = 0;
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                prefix[i][j] = prefix[i][j - 1] + mat[i - 1][j - 1] + prefix[i - 1][j] - prefix[i - 1][j - 1];
                int l = Math.min(i, j);
                for (int k = res + 1; k <= l; k++) {
                    int area = prefix[i][j] - prefix[i - k][j] - prefix[i][j - k] + prefix[i - k][j - k];
                    if (area <= threshold) {
                        res = Math.max(res, k);
                    } else {
                        break;
                    }
                }
            }
        }
        return res;
    }

}

性能

目标

给你一个二维整数数组 squares ，其中 squares[i] = [xi, yi, li] 表示一个与 x 轴平行的正方形的左下角坐标和正方形的边长。

找到一个最小的 y 坐标，它对应一条水平线，该线需要满足它以上正方形的总面积 等于 该线以下正方形的总面积。

答案如果与实际答案的误差在 10^-5 以内，将视为正确答案。

注意：正方形 可能会 重叠。重叠区域应该被 多次计数 。

示例 1：

输入： squares = [[0,0,1],[2,2,1]]
输出： 1.00000
解释：
任何在 y = 1 和 y = 2 之间的水平线都会有 1 平方单位的面积在其上方，1 平方单位的面积在其下方。最小的 y 坐标是 1。

示例 2：

输入： squares = [[0,0,2],[1,1,1]]
输出： 1.16667
解释：
面积如下：
线下的面积：7/6 * 2 (红色) + 1/6 (蓝色) = 15/6 = 2.5。
线上的面积：5/6 * 2 (红色) + 5/6 (蓝色) = 15/6 = 2.5。
由于线以上和线以下的面积相等，输出为 7/6 = 1.16667。

说明：

• 1 <= squares.length <= 5 * 10^4
• squares[i] = [xi, yi, li]
• squares[i].length == 3
• 0 <= xi, yi <= 10^9
• 1 <= li <= 10^9
• 所有正方形的总面积不超过 10^12。

思路

二维平面内有一些正方形，squares[i] = [xi, yi, li] 表示正方形坐下顶点坐标为 (xi, yi)，边长为 li。找到最小的 y 水平线，使得这些正方形在水平线上方的面积等于下方的面积，重叠部分的面积应被重复计算。

二分答案，计算上方与下方的面积。

代码

/**
 * @date 2026-01-13 9:08
 */
public class SeparateSquares3453 {

    public double separateSquares(int[][] squares) {
        double l = 0.0, r = 1000000000.0;
        double m = l + (r - l) / 2;
        while (l <= r) {
            if (check(squares, m)) {
                r = m - 0.00001;
            } else {
                l = m + 0.00001;
            }
            m = l + (r - l) / 2;
        }
        return l;
    }

    private boolean check(int[][] squares, double m) {
        double upperSum = 0.0, lowerSum = 0.0;
        for (int[] square : squares) {
            int y = square[1], l = square[2];
            if (y + l <= m) {
                lowerSum += (double) l * l;
            } else if (y >= m) {
                upperSum += (double) l * l;
            } else {
                upperSum += (double) l * (y + l - m);
                lowerSum += (double) l * (m - y);
            }
        }
        return upperSum <= lowerSum;
    }

}

性能

目标

给你一个下标从 0 开始的二维整数数组 events ，其中 events[i] = [startTimei, endTimei, valuei] 。第 i 个活动开始于 startTimei ，结束于 endTimei ，如果你参加这个活动，那么你可以得到价值 valuei 。你 最多 可以参加 两个时间不重叠 活动，使得它们的价值之和 最大 。

请你返回价值之和的 最大值 。

注意，活动的开始时间和结束时间是 包括 在活动时间内的，也就是说，你不能参加两个活动且它们之一的开始时间等于另一个活动的结束时间。更具体的，如果你参加一个活动，且结束时间为 t ，那么下一个活动必须在 t + 1 或之后的时间开始。

示例 1:

输入：events = [[1,3,2],[4,5,2],[2,4,3]]
输出：4
解释：选择绿色的活动 0 和 1 ，价值之和为 2 + 2 = 4 。

示例 2：

输入：events = [[1,3,2],[4,5,2],[1,5,5]]
输出：5
解释：选择活动 2 ，价值和为 5 。

示例 3：

输入：events = [[1,5,3],[1,5,1],[6,6,5]]
输出：8
解释：选择活动 0 和 2 ，价值之和为 3 + 5 = 8 。

说明：

• 2 <= events.length <= 10^5
• events[i].length == 3
• 1 <= startTimei <= endTimei <= 10^9
• 1 <= valuei <= 10^6

思路

有一个二维数组 events，events[i] 表示事件 i 的 (开始时间，结束时间，价值) 三元组，至多参加两个活动，这两个活动不能重叠 (结束时间与开始时间也不能重叠)，求参加活动的最大价值。

根据开始时间排序，二分查找第一个大于结束时间的下标，维护后缀最大值。

代码

/**
 * @date 2025-12-23 8:53
 */
public class MaxTwoEvents2054 {

    public int maxTwoEvents(int[][] events) {
        Arrays.sort(events, (a, b) -> a[0] - b[0]);
        int res = 0;
        int n = events.length;
        int[] suffix = new int[n + 1];
        for (int i = n - 1; i >= 0; i--) {
            suffix[i] = Math.max(suffix[i + 1], events[i][2]);
        }
        for (int[] event : events) {
            int index = bs(events, event[1]);
            res = Math.max(res, event[2] + suffix[index]);
        }
        return res;
    }

    public int bs(int[][] events, int target) {
        int l = 0;
        int r = events.length - 1;
        int m = l + (r - l) / 2;
        while (l <= r) {
            if (events[m][0] <= target) {
                l = m + 1;
            } else {
                r = m - 1;
            }
            m = l + (r - l) / 2;
        }
        return l;
    }

}

性能

目标

如果整数 x 满足：对于每个数位 d ，这个数位 恰好 在 x 中出现 d 次。那么整数 x 就是一个 数值平衡数 。

给你一个整数 n ，请你返回 严格大于 n 的 最小数值平衡数 。

示例 1：

输入：n = 1
输出：22
解释：
22 是一个数值平衡数，因为：
- 数字 2 出现 2 次 
这也是严格大于 1 的最小数值平衡数。

示例 2：

输入：n = 1000
输出：1333
解释：
1333 是一个数值平衡数，因为：
- 数字 1 出现 1 次。
- 数字 3 出现 3 次。 
这也是严格大于 1000 的最小数值平衡数。
注意，1022 不能作为本输入的答案，因为数字 0 的出现次数超过了 0 。

示例 3：

输入：n = 3000
输出：3133
解释：
3133 是一个数值平衡数，因为：
- 数字 1 出现 1 次。
- 数字 3 出现 3 次。 
这也是严格大于 3000 的最小数值平衡数。

说明：

• 0 <= n <= 10^6

思路

定义平衡数中每一位上数字的出现次数 cnt[d] = d，判断大于 n 的最小平衡数。

回溯构造 10^7 范围内的所有平衡数，然后二分查找。

官网题解是枚举所有大于 n 的整数，判断是否是平衡数，也可以预处理 (n, 1224444] 范围内的所有平衡数，然后二分查找。

代码

/**
 * @date 2025-10-24 9:12
 */
public class NextBeautifulNumber2048 {

    public int nextBeautifulNumber(int n) {
        return set.higher(n);
    }

    private static final TreeSet<Integer> set = new TreeSet<>();

    static {
        int[] cnt = new int[7];
        Arrays.setAll(cnt, i -> i);
        dfs(0, 0, 7, cnt);
    }

    public static void dfs(int cur, int l, int length, int[] cnt) {
        if (l > length + 1) {
            return;
        }
        boolean balance = true;
        for (int i = 1; i < cnt.length; i++) {
            if (cnt[i] != i && cnt[i] != 0) {
                balance = false;
                break;
            }
        }
        if (balance) {
            set.add(cur);
        }
        for (int i = 1; i < cnt.length; i++) {
            if (cnt[i] == 0) {
                continue;
            }
            cnt[i]--;
            dfs(cur * 10 + i, l + 1, length, cnt);
            cnt[i]++;
        }
    }

}

性能

目标

给你一个整数数组 nums 和两个整数 k 和 numOperations 。

你必须对 nums 执行 操作 numOperations 次。每次操作中，你可以：

• 选择一个下标 i ，它在之前的操作中 没有 被选择过。
• 将 nums[i] 增加范围 [-k, k] 中的一个整数。

在执行完所有操作以后，请你返回 nums 中出现 频率最高 元素的出现次数。

一个元素 x 的 频率 指的是它在数组中出现的次数。

示例 1：

输入：nums = [1,4,5], k = 1, numOperations = 2
输出：2
解释：
通过以下操作得到最高频率 2 ：
将 nums[1] 增加 0 ，nums 变为 [1, 4, 5] 。
将 nums[2] 增加 -1 ，nums 变为 [1, 4, 4] 。

示例 2：

输入：nums = [5,11,20,20], k = 5, numOperations = 1
输出：2
解释：
通过以下操作得到最高频率 2 ：
将 nums[1] 增加 0 。

说明：

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

思路

对数组 nums 执行 numOperations 次操作，每次操作可以选一个没有被操作过的元素，将其增加 [-k, k] 之间的整数，求元素值的最大出现次数。

对数组排序，并针对元素进行计数，枚举值域范围内的每一个值，二分查找左右 k 范围内的元素个数。

代码

/**
 * @date 2025-10-21 8:53
 */
public class MaxFrequency3346 {

    public int maxFrequency(int[] nums, int k, int numOperations) {
        int max = Arrays.stream(nums).max().getAsInt();
        int[] cnt = new int[max + 1];
        for (int num : nums) {
            cnt[num]++;
        }
        Arrays.sort(nums);
        int res = 1;
        for (int i = 1; i <= max; i++) {
            int l = lowerBound(nums, i - k);
            int r = upperBound(nums, i + k);
            res = Math.max(res, cnt[i] + Math.min(r - l + 1 - cnt[i], numOperations));
        }
        return res;
    }

    public int lowerBound(int[] nums, int target) {
        int r = nums.length - 1;
        int l = 0;
        int mid = l + (r - l) / 2;
        while (l <= r) {
            if (nums[mid] >= target) {
                r = mid - 1;
            } else {
                l = mid + 1;
            }
            mid = l + (r - l) / 2;
        }
        return l;
    }

    public int upperBound(int[] nums, int target) {
        int r = nums.length - 1;
        int l = 0;
        int mid = l + (r - l) / 2;
        while (l <= r) {
            if (nums[mid] <= target) {
                l = mid + 1;
            } else {
                r = mid - 1;
            }
            mid = l + (r - l) / 2;
        }
        return r;
    }

}

性能