标签： 数组

目标

一个数对 (a,b) 的 数对和 等于 a + b 。最大数对和 是一个数对数组中最大的 数对和 。

• 比方说，如果我们有数对 (1,5) ，(2,3) 和 (4,4)，最大数对和 为 max(1+5, 2+3, 4+4) = max(6, 5, 8) = 8 。

给你一个长度为 偶数 n 的数组 nums ，请你将 nums 中的元素分成 n / 2 个数对，使得：

• nums 中每个元素 恰好 在 一个 数对中，且
• 最大数对和 的值 最小 。

请你在最优数对划分的方案下，返回最小的 最大数对和 。

示例 1：

输入：nums = [3,5,2,3]
输出：7
解释：数组中的元素可以分为数对 (3,3) 和 (5,2) 。
最大数对和为 max(3+3, 5+2) = max(6, 7) = 7 。

示例 2：

输入：nums = [3,5,4,2,4,6]
输出：8
解释：数组中的元素可以分为数对 (3,5)，(4,4) 和 (6,2) 。
最大数对和为 max(3+5, 4+4, 6+2) = max(8, 8, 8) = 8 。

说明：

• n == nums.length
• 2 <= n <= 10^5
• n 是 偶数 。
• 1 <= nums[i] <= 10^5

思路

将长度为偶数的数组 nums 划分成若干数对，求这些数对和的最大值的最小值。

每种划分方案可以得到数对的最大值，取不同方案中最大值的最小值。

容易猜到划分方案应该是最小值与最大值组成数对，次小值与次大值组成数对，以此类推。

可以使用交换论证法来证明，如果存在一个更优的方案，那么可以通过 局部交换 操作，将其逐步调整为贪心方案，且每一步都不增加代价（或保持最优）。

代码

/**
 * @date 2026-01-26 11:32
 */
public class MinPairSum1877 {

    public int minPairSum(int[] nums) {
        Arrays.sort(nums);
        int n = nums.length;
        int res = 0;
        for (int i = 0; i < n / 2; i++) {
            res = Math.max(res, nums[i] + nums[n - 1 - i]);
        }
        return res;
    }

}

性能

目标

一个 k x k 的 幻方 指的是一个 k x k 填满整数的方格阵，且每一行、每一列以及两条对角线的和 全部相等 。幻方中的整数 不需要互不相同 。显然，每个 1 x 1 的方格都是一个幻方。

给你一个 m x n 的整数矩阵 grid ，请你返回矩阵中 最大幻方 的 尺寸 （即边长 k）。

示例 1：

输入：grid = [[7,1,4,5,6],[2,5,1,6,4],[1,5,4,3,2],[1,2,7,3,4]]
输出：3
解释：最大幻方尺寸为 3 。
每一行，每一列以及两条对角线的和都等于 12 。
- 每一行的和：5+1+6 = 5+4+3 = 2+7+3 = 12
- 每一列的和：5+5+2 = 1+4+7 = 6+3+3 = 12
- 对角线的和：5+4+3 = 6+4+2 = 12

示例 2：

输入：grid = [[5,1,3,1],[9,3,3,1],[1,3,3,8]]
输出：2

说明：

• m == grid.length
• n == grid[i].length
• 1 <= m, n <= 50
• 1 <= grid[i][j] <= 10^6

思路

找出 m x n 矩阵中的最大幻方的边长。

暴力枚举顶点与边长，判断是否是幻方。可以记录水平、垂直、主对角线和副对角线上的前缀和，方便幻方判断。另外边长可以从大到小枚举，是幻方就直接返回。

代码

/**
 * @date 2026-01-19 14:59
 */
public class LargestMagicSquare1895 {

    public int largestMagicSquare(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        int res = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                int l = Math.min(i, j) + 1;
                for (int k = res + 1; k <= l; k++) {
                    if (isMagicSquare(grid, i, j, k)) {
                        res = k;
                    }
                }
            }
        }
        return res;
    }

    public boolean isMagicSquare(int[][] grid, int x, int y, int l) {
        int diagonal1 = 0;
        int diagonal2 = 0;
        for (int k = 0; k < l; k++) {
            diagonal1 += grid[x - k][y - k];
            diagonal2 += grid[x - l + 1 + k][y - k];
        }
        if (diagonal1 != diagonal2) {
            return false;
        }

        for (int i = x - l + 1; i <= x; i++) {
            int sum = 0;
            for (int j = y - l + 1; j <= y; j++) {
                sum += grid[i][j];
            }
            if (sum != diagonal1) {
                return false;
            }
        }
        for (int j = y - l + 1; j <= y; j++) {
            int sum = 0;
            for (int i = x - l + 1; i <= x; i++) {
                sum += grid[i][j];
            }
            if (sum != diagonal1) {
                return false;
            }
        }
        return true;
    }

}

性能

目标

在二维平面上存在 n 个矩形。给你两个下标从 0 开始的二维整数数组 bottomLeft 和 topRight，两个数组的大小都是 n x 2 ，其中 bottomLeft[i] 和 topRight[i] 分别代表第 i 个矩形的 左下角 和 右上角 坐标。

我们定义 向右 的方向为 x 轴正半轴（x 坐标增加），向左 的方向为 x 轴负半轴（x 坐标减少）。同样地，定义 向上 的方向为 y 轴正半轴（y 坐标增加），向下 的方向为 y 轴负半轴（y 坐标减少）。

你可以选择一个区域，该区域由两个矩形的 交集 形成。你需要找出能够放入该区域 内 的 最大 正方形面积，并选择最优解。

返回能够放入交集区域的正方形的 最大 可能面积，如果矩形之间不存在任何交集区域，则返回 0。

示例 1：

输入：bottomLeft = [[1,1],[2,2],[3,1]], topRight = [[3,3],[4,4],[6,6]]
输出：1
解释：边长为 1 的正方形可以放入矩形 0 和矩形 1 的交集区域，或矩形 1 和矩形 2 的交集区域。因此最大面积是边长 * 边长，即 1 * 1 = 1。
可以证明，边长更大的正方形无法放入任何交集区域。

示例 2：

输入：bottomLeft = [[1,1],[2,2],[1,2]], topRight = [[3,3],[4,4],[3,4]]
输出：1
解释：边长为 1 的正方形可以放入矩形 0 和矩形 1，矩形 1 和矩形 2，或所有三个矩形的交集区域。因此最大面积是边长 * 边长，即 1 * 1 = 1。
可以证明，边长更大的正方形无法放入任何交集区域。
请注意，区域可以由多于两个矩形的交集构成。

示例 3：

输入：bottomLeft = [[1,1],[3,3],[3,1]], topRight = [[2,2],[4,4],[4,2]]
输出：0
解释：不存在相交的矩形，因此，返回 0 。

说明：

• n == bottomLeft.length == topRight.length
• 2 <= n <= 10^3
• bottomLeft[i].length == topRight[i].length == 2
• 1 <= bottomLeft[i][0], bottomLeft[i][1] <= 10^7
• 1 <= topRight[i][0], topRight[i][1] <= 10^7
• bottomLeft[i][0] < topRight[i][0]
• bottomLeft[i][1] < topRight[i][1]

思路

二维平面上有一些矩形，第 i 个矩形的左下坐标为 bottomLeft[i]，右上坐标为 topRight[i]，求其中任意两个矩形交集区域的最大正方形面积。

针对每一个矩形，枚举其它矩形，计算交集区域最大的正方形边长。

令 bl1 表示矩形 1 的左下坐标，tr1 表示矩形 1 的右上坐标，bl2、tr2 同理。

• 相交区域的垂直边长为 Math.min(tr1[1], tr2[1]) - Math.max(bl1[1], bl2[1])
• 相交区域的水平边长为 Math.min(tr1[0], tr2[0]) - Math.max(bl1[0], bl2[0])

代码

/**
 * @date 2026-01-21 9:08
 */
public class LargestSquareArea3047 {

    public long largestSquareArea_v1(int[][] bottomLeft, int[][] topRight) {
        long res = 0L;
        int n = bottomLeft.length;
        for (int i = 0; i < n; i++) {
            int[] bl1 = bottomLeft[i], tr1 = topRight[i];
            for (int j = i + 1; j < n; j++) {
                int[] bl2 = bottomLeft[j], tr2 = topRight[j];
                res = Math.max(res, Math.min(Math.min(tr1[1], tr2[1]) - Math.max(bl1[1], bl2[1]), Math.min(tr1[0], tr2[0]) - Math.max(bl1[0], bl2[0])));
            }
        }
        return res * res;
    }

}

性能

目标

有一个大型的 (m - 1) x (n - 1) 矩形田地，其两个对角分别是 (1, 1) 和 (m, n) ，田地内部有一些水平栅栏和垂直栅栏，分别由数组 hFences 和 vFences 给出。

水平栅栏为坐标 (hFences[i], 1) 到 (hFences[i], n)，垂直栅栏为坐标 (1, vFences[i]) 到 (m, vFences[i]) 。

返回通过 移除 一些栅栏（可能不移除）所能形成的最大面积的 正方形 田地的面积，或者如果无法形成正方形田地则返回 -1。

由于答案可能很大，所以请返回结果对 10^9 + 7 取余 后的值。

注意：田地外围两个水平栅栏（坐标 (1, 1) 到 (1, n) 和坐标 (m, 1) 到 (m, n) ）以及两个垂直栅栏（坐标 (1, 1) 到 (m, 1) 和坐标 (1, n) 到 (m, n) ）所包围。这些栅栏 不能 被移除。

示例 1：

输入：m = 4, n = 3, hFences = [2,3], vFences = [2]
输出：4
解释：移除位于 2 的水平栅栏和位于 2 的垂直栅栏将得到一个面积为 4 的正方形田地。

示例 2：

输入：m = 6, n = 7, hFences = [2], vFences = [4]
输出：-1
解释：可以证明无法通过移除栅栏形成正方形田地。

说明：

• 3 <= m, n <= 10^9
• 1 <= hFences.length, vFences.length <= 600
• 1 < hFences[i] < m
• 1 < vFences[i] < n
• hFences 和 vFences 中的元素是唯一的。

思路

有一个 (m - 1) x (n - 1) 矩形田地，左上角坐标为 (1, 1)，右下角坐标为 (m, n)，田地内部有一些栅栏，水平栅栏 i 的纵坐标为 hFences[i]，垂直栅栏 j 的横坐标为 vFences[j]。可以移除一些栅栏，求能够形成的最大正方形的面积。

使用哈希表分别记录水平与垂直方向可能的间隔，找到最大相等间隔，相乘即可。

代码

/**
 * @date 2026-01-16 8:49
 */
public class MaximizeSquareArea2975 {

    public int maximizeSquareArea(int m, int n, int[] hFences, int[] vFences) {
        Set<Integer> hq = getInterval(m, hFences);
        Set<Integer> vq = getInterval(n, vFences);
        hq.retainAll(vq);
        if (hq.size() == 0) {
            return -1;
        }
        long res = 0;
        int mod = 1000000007;
        for (Integer num : hq) {
            res = Math.max(res, num);
        }
        return (int) (res * res % mod);
    }

    private Set<Integer> getInterval(int edge, int[] fences) {
        Arrays.sort(fences);
        Set<Integer> set = new HashSet<>();
        int n = fences.length;
        for (int i = 0; i < n; i++) {
            set.add(fences[i] - 1);
            set.add(edge - fences[i]);
            for (int j = i + 1; j < n; j++) {
                set.add(fences[j] - fences[i]);
            }
        }
        set.add(edge - 1);
        return set;
    }

}

性能

目标

给你一个长度为 n 的数组 happiness ，以及一个 正整数 k 。

n 个孩子站成一队，其中第 i 个孩子的 幸福值 是 happiness[i] 。你计划组织 k 轮筛选从这 n 个孩子中选出 k 个孩子。

在每一轮选择一个孩子时，所有 尚未 被选中的孩子的 幸福值 将减少 1 。注意，幸福值 不能 变成负数，且只有在它是正数的情况下才会减少。

选择 k 个孩子，并使你选中的孩子幸福值之和最大，返回你能够得到的 最大值 。

示例 1：

输入：happiness = [1,2,3], k = 2
输出：4
解释：按以下方式选择 2 个孩子：
- 选择幸福值为 3 的孩子。剩余孩子的幸福值变为 [0,1] 。
- 选择幸福值为 1 的孩子。剩余孩子的幸福值变为 [0] 。注意幸福值不能小于 0 。
所选孩子的幸福值之和为 3 + 1 = 4 。

示例 2：

输入：happiness = [1,1,1,1], k = 2
输出：1
解释：按以下方式选择 2 个孩子：
- 选择幸福值为 1 的任意一个孩子。剩余孩子的幸福值变为 [0,0,0] 。
- 选择幸福值为 0 的孩子。剩余孩子的幸福值变为 [0,0] 。
所选孩子的幸福值之和为 1 + 0 = 1 。

示例 3：

输入：happiness = [2,3,4,5], k = 1
输出：5
解释：按以下方式选择 1 个孩子：
- 选择幸福值为 5 的孩子。剩余孩子的幸福值变为 [1,2,3] 。
所选孩子的幸福值之和为 5 。

说明：

• 1 <= n == happiness.length <= 2 * 10^5
• 1 <= happiness[i] <= 10^8
• 1 <= k <= n

思路

n 个孩子站成一排，happiness[i] 表示第 i 个孩子的幸福值，从中选 k 个孩子，每选择一个孩子，剩余孩子的幸福值会减少 1（但不会是负值），求所选孩子幸福值之和的最大值。

贪心策略，优先选幸福值最大的，因为下限为 0，如果放后面选减的更多。

代码

/**
 * @date 2025-12-25 8:51
 */
public class MaximumHappinessSum3075 {

    public long maximumHappinessSum(int[] happiness, int k) {
        long res = 0;
        int sub = 0;
        Arrays.sort(happiness);
        int n = happiness.length;
        for (int i = n - 1; sub < k; i--) {
            res += Math.max(0, happiness[i] - sub++);
        }
        return res;
    }
}

性能

目标

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

选取一个删除索引序列，对于 strs 中的每个字符串，删除对应每个索引处的字符。

比如，有 strs = ["abcdef", "uvwxyz"]，删除索引序列 {0, 2, 3}，删除后 strs 为["bef", "vyz"]。

假设，我们选择了一组删除索引 answer，那么在执行删除操作之后，最终得到的数组的元素是按 字典序（strs[0] <= strs[1] <= strs[2] ... <= strs[n - 1]）排列的，然后请你返回 answer.length 的最小可能值。

示例 1：

输入：strs = ["ca","bb","ac"]
输出：1
解释： 
删除第一列后，strs = ["a", "b", "c"]。
现在 strs 中元素是按字典排列的 (即，strs[0] <= strs[1] <= strs[2])。
我们至少需要进行 1 次删除，因为最初 strs 不是按字典序排列的，所以答案是 1。

示例 2：

输入：strs = ["xc","yb","za"]
输出：0
解释：
strs 的列已经是按字典序排列了，所以我们不需要删除任何东西。
注意 strs 的行不需要按字典序排列。
也就是说，strs[0][0] <= strs[0][1] <= ... 不一定成立。

示例 3：

输入：strs = ["zyx","wvu","tsr"]
输出：3
解释：
我们必须删掉每一列。

说明：

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

思路

有一个元素长度相同的字符串数组 strs，通过删除列使得字符串元素按字典序非严格递增，返回删除的最少列数。

首先如果按列不是非严格递增的，那么一定要删除该列。然后，如果是非严格递增的，需要继续考查相同行后续列的字典序。

维护同一列中相同字母的行标列表 sameList，初始时包括所有行，如果需要删除就直接进入下一列循环，否则遍历 sameList 判断是否是升序（相同的字母组内比较），同时记录当前列相同的行标，如果 sameList 列表为空则退出。

代码

/**
 * @date 2025-12-21 19:24
 */
public class MinDeletionSize955 {

    public int minDeletionSize(String[] strs) {
        int n = strs.length;
        int m = strs[0].length();
        List<Integer> indexList = new ArrayList<>(n);
        for (int i = 0; i < n - 1; i++) {
            indexList.add(i);
        }
        int res = 0;
        here:
        for (int i = 0; i < m; i++) {
            if (indexList.size() == 0) {
                break;
            }
            List<Integer> tmp = new ArrayList<>();
            for (Integer k : indexList) {
                char cur = strs[k].charAt(i);
                char next = strs[k + 1].charAt(i);
                if (cur > next) {
                    res++;
                    continue here;
                } else if (cur == next) {
                    tmp.add(k);
                }
            }
            indexList = tmp;
        }
        return res;
    }

}

性能