标签： 贪心算法

目标

给你一个 n x n 的整数方阵 matrix 。你可以执行以下操作 任意次 ：

• 选择 matrix 中 相邻 两个元素，并将它们都 乘以 -1 。

如果两个元素有 公共边 ，那么它们就是 相邻 的。

你的目的是 最大化 方阵元素的和。请你在执行以上操作之后，返回方阵的 最大 和。

示例 1：

输入：matrix = [[1,-1],[-1,1]]
输出：4
解释：我们可以执行以下操作使和等于 4 ：
- 将第一行的 2 个元素乘以 -1 。
- 将第一列的 2 个元素乘以 -1 。

示例 2：

输入：matrix = [[1,2,3],[-1,-2,-3],[1,2,3]]
输出：16
解释：我们可以执行以下操作使和等于 16 ：
- 将第二行的最后 2 个元素乘以 -1 。

说明：

• n == matrix.length == matrix[i].length
• 2 <= n <= 250
• -10^5 <= matrix[i][j] <= 10^5

思路

有一个 n x n 矩阵，每次操作可以将相邻的元素乘以 -1，执行操作任意次，求能够得到的最大方阵和。

经过观察发现，可以将任意两个元素乘以 -1，只需对路径上的每个元素执行操作，改变 (cur, next) 的符号，中间每个元素的符号都被改变了两次，即首尾元素改变了符号。

只需判断矩阵中负数的个数，如果是偶数，可以将负数全部变为相反数；如果是奇数，则需要找到最小的非负数，将其变为负数，其余元素全部变为非负数。

代码

/**
 * @date 2026-01-05 9:07
 */
public class MaxMatrixSum1975 {

    public long maxMatrixSum(int[][] matrix) {
        long res = 0L;
        int negativeCnt = 0;
        int min = Integer.MAX_VALUE;
        for (int[] row : matrix) {
            for (int col : row) {
                res += Math.abs(col);
                min = Math.min(min, Math.abs(col));
                if (col < 0) {
                    negativeCnt++;
                }
            }
        }
        if (negativeCnt % 2 == 1) {
            res -= 2 * min;
        }
        return res;
    }

}

性能

目标

给你一个长度为 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;
    }

}

性能

目标

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

返回 nums 中一个 非空子数组 的 最大 和，要求该子数组的长度可以 被 k 整除。

示例 1：

输入： nums = [1,2], k = 1
输出： 3
解释：
子数组 [1, 2] 的和为 3，其长度为 2，可以被 1 整除。

示例 2：

输入： nums = [-1,-2,-3,-4,-5], k = 4
输出： -10
解释：
满足题意且和最大的子数组是 [-1, -2, -3, -4]，其长度为 4，可以被 4 整除。

示例 3：

输入： nums = [-5,1,2,-3,4], k = 2
输出： 4
解释：
满足题意且和最大的子数组是 [1, 2, -3, 4]，其长度为 4，可以被 2 整除。

说明：

• 1 <= k <= nums.length <= 2 * 10^5
• -10^9 <= nums[i] <= 10^9

思路

计算长度能被 k 整除的子数组的最大元素和。

核心点是维护同余前缀和的最小值。

也有网友使用滑窗加动态规划来做，滑窗计算 长度为 k 的子数组和，动态规划累加长度 m * k 的子数组和，这里使用了贪心策略，如果前面的子数组和小于 0，直接重置为 0。

代码

/**
 * @date 2025-11-27 9:06
 */
public class MaxSubarraySum3381 {

    public long maxSubarraySum(int[] nums, int k) {
        int n = nums.length;
        long[] prefix = new long[n + 1];
        for (int i = 1; i <= n; i++) {
            prefix[i] = prefix[i - 1] + nums[i - 1];
        }
        long[] minPrefix = new long[k];
        Arrays.fill(minPrefix, Long.MAX_VALUE / 2);
        long res = Long.MIN_VALUE;
        for (int i = 0; i <= n; i++) {
            int rem = i % k;
            res = Math.max(res, prefix[i] - minPrefix[rem]);
            minPrefix[rem] = Math.min(minPrefix[rem], prefix[i]);
        }
        return res;
    }

}

性能

目标

给你一个整数数组 nums，请你找出并返回能被三整除的元素 最大和。

示例 1：

输入：nums = [3,6,5,1,8]
输出：18
解释：选出数字 3, 6, 1 和 8，它们的和是 18（可被 3 整除的最大和）。

示例 2：

输入：nums = [4]
输出：0
解释：4 不能被 3 整除，所以无法选出数字，返回 0。

示例 3：

输入：nums = [1,2,3,4,4]
输出：12
解释：选出数字 1, 3, 4 以及 4，它们的和是 12（可被 3 整除的最大和）。

说明：

• 1 <= nums.length <= 4 * 10^4
• 1 <= nums[i] <= 10^4

思路

求整数数组中元素的最大和，要求和能被 3 整除。

• 如果和 sum % 3 == 1，可以去掉一个模 3 余 1 的最小元素，或者 两个模 3 余 2 的最小元素
• 如果和 sum % 3 == 2，可以去掉一个模 3 余 2 的最小元素，或者 两个模 3 余 1 的最小元素

代码

/**
 * @date 2025-11-23 20:46
 */
public class MaxSumDivThree1262 {

    public int maxSumDivThree(int[] nums) {
        int res = 0;
        PriorityQueue<Integer> q1 = new PriorityQueue<>();
        PriorityQueue<Integer> q2 = new PriorityQueue<>();
        for (int num : nums) {
            res += num;
            if (num % 3 == 1) {
                q1.offer(num);
            } else if (num % 3 == 2) {
                q2.offer(num);
            }
        }
        int mod = res % 3;
        if (mod == 1) {
            int sub = q1.size() == 0 ? 100000 : q1.peek();
            if (q2.size() > 1) {
                sub = Math.min(sub, q2.poll() + q2.poll());
            }
            res -= sub;
        } else if (mod == 2) {
            int sub = q2.size() == 0 ? 100000 : q2.peek();
            if (q1.size() > 1) {
                sub = Math.min(sub, q1.poll() + q1.poll());
            }
            res -= sub;
        }
        return res;
    }
}

性能

目标

给你一个 二进制字符串 s。

你可以对这个字符串执行 任意次 下述操作：

• 选择字符串中的任一下标 i（ i + 1 < s.length ），该下标满足 s[i] == '1' 且 s[i + 1] == '0'。
• 将字符 s[i] 向 右移 直到它到达字符串的末端或另一个 '1'。例如，对于 s = "010010"，如果我们选择 i = 1，结果字符串将会是 s = "000110"。

返回你能执行的 最大 操作次数。

示例 1：

输入： s = "1001101"
输出： 4
解释：
可以执行以下操作：
选择下标 i = 0。结果字符串为 s = "0011101"。
选择下标 i = 4。结果字符串为 s = "0011011"。
选择下标 i = 3。结果字符串为 s = "0010111"。
选择下标 i = 2。结果字符串为 s = "0001111"。

示例 2：

输入： s = "00111"
输出： 0

说明：

• 1 <= s.length <= 10^5
• s[i] 为 '0' 或 '1'。

思路

有一个二进制字符串 s，每次操作可以选择一个下标 i，满足 s[i] == '1' 且 s[i + 1] == '0'，将 s[i] 向右移直到遇到另一个 1 或者到达末尾，返回可以执行的最大操作次数。

要使操作次数最大，每组相邻的 0 都要为其前面的 1 提供一次操作。换句话说操作尽量不要让右侧的 0 过早的合并，累加每组相邻的 0 前面 1 的个数即可。

计算前缀 1 个数，正序遍历，第一次遇到 0 时，就加上前面 1 的个数，跳过相邻的 0（因为每次操作都要移到最右侧，相邻的 0 对每个 1 只能贡献一次操作）。

代码

/**
 * @date 2025-11-13 8:44
 */
public class MaxOperations3228 {

    public int maxOperations(String s) {
        int n = s.length();
        char[] chars = s.toCharArray();
        int[] prefix = new int[n + 1];
        int res = 0;
        for (int i = 1; i <= n; i++) {
            prefix[i] = prefix[i - 1] + (chars[i - 1] - '0');
        }
        int i = 0;
        while (i < n) {
            if (chars[i] == '0') {
                res += prefix[i];
            }
            while (i < n && chars[i++] == '0') {
            }
        }
        return res;
    }

}

性能