shelterofly

3310.移除可疑的方法

目标

你正在维护一个项目，该项目有 n 个方法，编号从 0 到 n - 1。

给你两个整数 n 和 k，以及一个二维整数数组 invocations，其中 invocations[i] = [ai, bi] 表示方法 ai 调用了方法 bi。

已知如果方法 k 存在一个已知的 bug。那么方法 k 以及它直接或间接调用的任何方法都被视为可疑方法，我们需要从项目中移除这些方法。

只有当一组方法没有被这组之外的任何方法调用时，这组方法才能被移除。

返回一个数组，包含移除所有可疑方法后剩下的所有方法。你可以以任意顺序返回答案。如果无法移除所有可疑方法，则不移除任何方法。

示例 1:

输入: n = 4, k = 1, invocations = [[1,2],[0,1],[3,2]]
输出: [0,1,2,3]
解释:
方法 2 和方法 1 是可疑方法，但它们分别直接被方法 3 和方法 0 调用。由于方法 3 和方法 0 不是可疑方法，我们无法移除任何方法，故返回所有方法。

示例 2:

输入: n = 5, k = 0, invocations = [[1,2],[0,2],[0,1],[3,4]]
输出: [3,4]
解释:
方法 0、方法 1 和方法 2 是可疑方法，且没有被任何其他方法直接调用。我们可以移除它们。

示例 3:

输入: n = 3, k = 2, invocations = [[1,2],[0,1],[2,0]]
输出: []
解释:
所有方法都是可疑方法。我们可以移除它们。

说明:

1 <= n <= 10^5
0 <= k <= n - 1
0 <= invocations.length <= 2 * 10^5
invocations[i] == [ai, bi]
0 <= ai, bi <= n - 1
ai != bi
invocations[i] != invocations[j]

思路

有 n 个方法，编号为 0 ~ n - 1，invocations[i] = [ai, bi] 表示方法 ai 调用了方法 bi。已知方法 k 是可疑的，所有被 k 直接或间接调用的方法也都是可疑的。这些可疑方法如果没有被其它非可疑方法调用可以全部移除，返回剩余的方法。

先标记 k 直接或间接调用的方法，再从所有非可疑方法出发，判断是否会调用可疑方法。如果会调用，不可移除，否则直接返回所有非可疑方法。

代码


/**
 * @date 2026-08-05 9:17
 */
public class RemainingMethods3310 {

    public List<Integer> remainingMethods(int n, int k, int[][] invocations) {
        List<Integer>[] g = new ArrayList[n];
        Arrays.setAll(g, x -> new ArrayList<>());
        for (int[] i : invocations) {
            g[i[0]].add(i[1]);
        }
        boolean[] remove = new boolean[n];
        boolean[] visited = new boolean[n];
        dfs(k, g, remove);
        boolean canRemove = true;
        for (int i = 0; i < n; i++) {
            if (remove[i]) {
                continue;
            }
            if (dfs(i, g, visited, remove)) {
                canRemove = false;
            }
        }
        List<Integer> res = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            if (!canRemove) {
                res.add(i);
            } else if (!remove[i]) {
                res.add(i);
            }
        }
        return res;
    }

    public void dfs(int m, List<Integer>[] g, boolean[] remove) {
        if (remove[m]) {
            return;
        }
        remove[m] = true;
        for (Integer next : g[m]) {
            dfs(next, g, remove);
        }
    }

    public boolean dfs(int m, List<Integer>[] g, boolean[] visited, boolean[] remove) {
        visited[m] = true;
        if (remove[m]) {
            return true;
        }
        boolean res = false;
        for (Integer next : g[m]) {
            if (!visited[next]) {
                res = res || dfs(next, g, visited, remove);
            }
        }
        return res;
    }

}

性能

3731.找出缺失的元素

目标

给你一个整数数组 nums ，数组由若干互不相同的整数组成。

数组 nums 原本包含了某个范围内的所有整数。但现在，其中可能缺失部分整数。

该范围内的最小整数和最大整数仍然存在于 nums 中。

返回一个有序列表，包含该范围内缺失的所有整数，并按从小到大排序。如果没有缺失的整数，返回一个空列表。

示例 1：

输入： nums = [1,4,2,5]
输出： [3]
解释：
最小整数为 1，最大整数为 5，因此完整的范围应为 [1,2,3,4,5]。其中只有 3 缺失。

示例 2：

输入： nums = [7,8,6,9]
输出： []
解释：
最小整数为 6，最大整数为 9，因此完整的范围为 [6,7,8,9]。所有整数均已存在，因此没有缺失的整数。

示例 3：

输入： nums = [5,1]
输出： [2,3,4]
解释：
最小整数为 1，最大整数为 5，因此完整的范围应为 [1,2,3,4,5]。缺失的整数为 2、3 和 4。

说明：

2 <= nums.length <= 100
1 <= nums[i] <= 100

思路

有一个元素互不相同的数组，原本包含了 [min, max] 之间的所有整数，现在缺失了 (min, max) 中的一些元素，找到并返回缺失的元素。

首先找到数组的 min 与 max，将元素放入哈希表，遍历 (min, max) 判断数字是否在集合中。

代码


/**
 * @date 2026-08-04 8:49
 */
public class FindMissingElements3731 {

    public List<Integer> findMissingElements(int[] nums) {
        int min = 101, max = 0;
        Set<Integer> set = new HashSet<>();
        for (int num : nums) {
            min = Math.min(min, num);
            max = Math.max(max, num);
            set.add(num);
        }
        List<Integer> res = new ArrayList<>();
        for (int i = min + 1; i < max; i++) {
            if (!set.contains(i)) {
                res.add(i);
            }
        }
        return res;
    }
}

性能

1406.石子游戏III

目标

Alice 和 Bob 继续他们的石子游戏。几堆石子排成一行，每堆石子都对应一个得分，由数组 stoneValue 给出。

Alice 和 Bob 轮流取石子，Alice 总是先开始。在每个玩家的回合中，该玩家可以拿走剩下石子中的的前 1、2 或 3 堆石子。比赛一直持续到所有石头都被拿走。

每个玩家的最终得分为他所拿到的每堆石子的对应得分之和。每个玩家的初始分数都是 0 。

比赛的目标是决出最高分，得分最高的选手将会赢得比赛，比赛也可能会出现平局。

假设 Alice 和 Bob 都采取最优策略。

如果 Alice 赢了就返回 "Alice" ，Bob 赢了就返回 "Bob"，分数相同返回 "Tie" 。

示例 1：

输入：values = [1,2,3,7]
输出："Bob"
解释：Alice 总是会输，她的最佳选择是拿走前三堆，得分变成 6 。但是 Bob 的得分为 7，Bob 获胜。

示例 2：

输入：values = [1,2,3,-9]
输出："Alice"
解释：Alice 要想获胜就必须在第一个回合拿走前三堆石子，给 Bob 留下负分。
如果 Alice 只拿走第一堆，那么她的得分为 1，接下来 Bob 拿走第二、三堆，得分为 5 。之后 Alice 只能拿到分数 -9 的石子堆，输掉比赛。
如果 Alice 拿走前两堆，那么她的得分为 3，接下来 Bob 拿走第三堆，得分为 3 。之后 Alice 只能拿到分数 -9 的石子堆，同样会输掉比赛。
注意，他们都应该采取 最优策略 ，所以在这里 Alice 将选择能够使她获胜的方案。

示例 3：

输入：values = [1,2,3,6]
输出："Tie"
解释：Alice 无法赢得比赛。如果她决定选择前三堆，她可以以平局结束比赛，否则她就会输。

说明：

1 <= stoneValue.length <= 5 * 10^4
-1000 <= stoneValue[i] <= 1000

思路

几堆石子排成一排，stoneValue[i] 表示第 i 堆石子的个数。Alice 与 Bob 轮流取石子，Alice 先取，每次可以从剩余的石子堆中取走前 1、2 或者 3 堆石子，直到石子均被取走。返回结束时取走石子最多的玩家姓名，如果相同则返回 Tie。

定义 dp[i] 表示剩余 [i, n - 1] 堆石子，先手与后手所能获得的石子个数之差的最大值。dp[i] = max(sumj - dp[j + 1])，其中 j ∈ [i, min(i + 2, n - 1)]，sumj 表示 [i, j] 的石子堆数量之和。倒序遍历，初始化 dp[n] = 0, dp[n - 1] = stoneValue[n - 1]。

代码


/**
 * @date 2026-08-03 15:22
 */
public class StoneGameIII1406 {

    public String stoneGameIII(int[] stoneValue) {
        int n = stoneValue.length;
        int[] dp = new int[n + 1];
        Arrays.fill(dp, Integer.MIN_VALUE);
        dp[n] = 0;
        dp[n - 1] = stoneValue[n - 1];
        for (int i = n - 1; i >= 0; i--) {
            int sum = 0;
            for (int j = i; j < Math.min(n, i + 3); j++) {
                sum += stoneValue[j];
                dp[i] = Math.max(dp[i], sum - dp[j + 1]);
            }
        }
        if (dp[0] == 0) {
            return "Tie";
        }
        return dp[0] > 0 ? "Alice" : "Bob";
    }
}

性能

877.石子游戏

目标

Alice 和 Bob 用几堆石子在做游戏。一共有偶数堆石子，排成一行；每堆都有正整数颗石子，数目为 piles[i] 。

游戏以谁手中的石子最多来决出胜负。石子的总数是奇数，所以没有平局。

Alice 和 Bob 轮流进行，Alice 先开始。每回合，玩家从行的开始或结束处取走整堆石头。这种情况一直持续到没有更多的石子堆为止，此时手中石子最多的玩家获胜。

假设 Alice 和 Bob 都发挥出最佳水平，当 Alice 赢得比赛时返回 true ，当 Bob 赢得比赛时返回 false 。

示例 1：

输入：piles = [5,3,4,5]
输出：true
解释：
Alice 先开始，只能拿前 5 颗或后 5 颗石子 。
假设他取了前 5 颗，这一行就变成了 [3,4,5] 。
如果 Bob 拿走前 3 颗，那么剩下的是 [4,5]，Alice 拿走后 5 颗赢得 10 分。
如果 Bob 拿走后 5 颗，那么剩下的是 [3,4]，Alice 拿走后 4 颗赢得 9 分。
这表明，取前 5 颗石子对 Alice 来说是一个胜利的举动，所以返回 true 。

示例 2：

输入：piles = [3,7,2,3]
输出：true

说明：

2 <= piles.length <= 500
piles.length 是偶数
1 <= piles[i] <= 500
sum(piles[i]) 是奇数

思路

有偶数堆石子排成一行，piles[i] 表示第 i 堆石子的数量，石子总数为奇数。从 Alice 开始，与 Bob 轮流取走左侧或右侧的整堆石子，直到取走所有石子堆为止。获得石子最多的玩家获胜。假设 Alice 与 Bob 都能做出最优的选择，判断 Alice 能否获胜。

定义 dp[i][j] 表示剩余石堆为 [i, j] 时，先手与后手获得的石子数量之差的最大值。dp[i][j] = max(piles[i] - dp[i + 1][j], piles[j] - dp[i][j - 1])。

先手 A 选择 i，剩余问题变成 B 先手 [i + 1, j]，而当前问题的先手是 A，剩余问题则是 B - A，应该取相反数。
先手 A 选择 j 同理。

外层倒序遍历，内存正序遍历。因为 i 依赖 i + 1，j 依赖 j - 1。初始化 dp[i][i] = pilesp[i]。

本题使用了空间优化，当前状态是从下方与左侧转移而来，从右下角到左上对角线开始，从左向右更新。每次状态更新只用到了下方与左侧的值，因此可以使用滚动数组保存下方的值。

先手玩家必定可以获胜，首先石子总数为奇数（不可能平局），奇数堆与偶数堆的石子数量必定不同，先手可以控制自己只选择偶数堆或者奇数堆，因此必胜。

因为开始时首尾的奇偶性不同，偶，……，奇，如果奇数堆的石子更多，那么先手就选奇数堆，这时留给后手的只有首尾的两个偶数下标。

代码


/**
 * @date 2026-08-03 14:45
 */
public class StoneGame877 {

    public boolean stoneGame_v1(int[] piles) {
        return true;
    }

    public boolean stoneGame(int[] piles) {
        int n = piles.length;
        int[] dp = new int[n];
        for (int i = n - 1; i >= 0; i--) {
            dp[i] = piles[i];
            for (int j = i + 1; j < n; j++) {
                dp[j] = Math.max(piles[i] - dp[j], piles[j] - dp[j - 1]);
            }
        }
        return dp[n - 1] > 0;
    }
}

性能

486.预测赢家

目标

给你一个整数数组 nums 。玩家 1 和玩家 2 基于这个数组设计了一个游戏。

玩家 1 和玩家 2 轮流进行自己的回合，玩家 1 先手。开始时，两个玩家的初始分值都是 0 。每一回合，玩家从数组的任意一端取一个数字（即，nums[0] 或 nums[nums.length - 1]），取到的数字将会从数组中移除（数组长度减 1 ）。玩家选中的数字将会加到他的得分上。当数组中没有剩余数字可取时，游戏结束。

如果玩家 1 能成为赢家，返回 true 。如果两个玩家得分相等，同样认为玩家 1 是游戏的赢家，也返回 true 。你可以假设每个玩家的玩法都会使他的分数最大化。

示例 1：

输入：nums = [1,5,2]
输出：false
解释：一开始，玩家 1 可以从 1 和 2 中进行选择。
如果他选择 2（或者 1 ），那么玩家 2 可以从 1（或者 2 ）和 5 中进行选择。如果玩家 2 选择了 5 ，那么玩家 1 则只剩下 1（或者 2 ）可选。 
所以，玩家 1 的最终分数为 1 + 2 = 3，而玩家 2 为 5 。
因此，玩家 1 永远不会成为赢家，返回 false 。

示例 2：

输入：nums = [1,5,233,7]
输出：true
解释：玩家 1 一开始选择 1 。然后玩家 2 必须从 5 和 7 中进行选择。无论玩家 2 选择了哪个，玩家 1 都可以选择 233 。
最终，玩家 1（234 分）比玩家 2（12 分）获得更多的分数，所以返回 true，表示玩家 1 可以成为赢家。

说明：

1 <= nums.length <= 20
0 <= nums[i] <= 10^7

思路

有一个整数数组 nums，玩家1 先手，从数组任意一端取走一个元素累加到他的得分上，最终积分高的玩家获胜（如果积分相同则先手玩家获胜），每个玩家的玩法都会使他的积分最大，判断 玩家1 能否取得胜利。

定义 dp[i][j] 表示子数组 nums[i:j] 先手玩家与后手玩家所能获得的最大积分之差的最大值。dp[i][j] = max(nums[i] - dp[i + 1][j], nums[j] - dp[i][j - 1])。

代码


/**
 * @date 2026-08-03 14:12
 */
public class PredictTheWinner486 {

    public boolean predictTheWinner_v1(int[] nums) {
        int n = nums.length;
        int[][] dp = new int[n][n];
        for (int i = n - 1; i >= 0; i--) {
            dp[i][i] = nums[i];
            for (int j = i + 1; j < n; j++) {
                dp[i][j] = Math.max(nums[i] - dp[i + 1][j], nums[j] - dp[i][j - 1]);
            }
        }
        return dp[0][n - 1] >= 0;
    }

}

性能

3016.输入单词需要的最少按键次数II

目标

给你一个字符串 word，由小写英文字母组成。

电话键盘上的按键与不同小写英文字母集合相映射，可以通过按压按键来组成单词。例如，按键 2 对应 ["a","b","c"]，我们需要按一次键来输入 "a"，按两次键来输入 "b"，按三次键来输入 "c"。

现在允许你将编号为 2 到 9 的按键重新映射到不同字母集合。每个按键可以映射到任意数量的字母，但每个字母必须恰好映射到一个按键上。你需要找到输入字符串 word 所需的最少按键次数。

返回重新映射按键后输入 word 所需的最少按键次数。

下面给出了一种电话键盘上字母到按键的映射作为示例。注意 1，*，# 和 0 不对应任何字母。

示例 1：

输入：word = "abcde"
输出：5
解释：图片中给出的重新映射方案的输入成本最小。
"a" -> 在按键 2 上按一次
"b" -> 在按键 3 上按一次
"c" -> 在按键 4 上按一次
"d" -> 在按键 5 上按一次
"e" -> 在按键 6 上按一次
总成本为 1 + 1 + 1 + 1 + 1 = 5 。
可以证明不存在其他成本更低的映射方案。

示例 2：

输入：word = "xyzxyzxyzxyz"
输出：12
解释：图片中给出的重新映射方案的输入成本最小。
"x" -> 在按键 2 上按一次
"y" -> 在按键 3 上按一次
"z" -> 在按键 4 上按一次
总成本为 1 * 4 + 1 * 4 + 1 * 4 = 12 。
可以证明不存在其他成本更低的映射方案。
注意按键 9 没有映射到任何字母：不必让每个按键都存在与之映射的字母，但是每个字母都必须映射到按键上。

示例 3：

输入：word = "aabbccddeeffgghhiiiiii"
输出：24
解释：图片中给出的重新映射方案的输入成本最小。
"a" -> 在按键 2 上按一次
"b" -> 在按键 3 上按一次
"c" -> 在按键 4 上按一次
"d" -> 在按键 5 上按一次
"e" -> 在按键 6 上按一次
"f" -> 在按键 7 上按一次
"g" -> 在按键 8 上按一次
"h" -> 在按键 9 上按两次
"i" -> 在按键 9 上按一次
总成本为 1 * 2 + 1 * 2 + 1 * 2 + 1 * 2 + 1 * 2 + 1 * 2 + 1 * 2 + 2 * 2 + 6 * 1 = 24 。
可以证明不存在其他成本更低的映射方案。

说明：

1 <= word.length <= 10^5
word 仅由小写英文字母组成。

思路

可以将 26 个字母映射到 2 ~ 9 按键上，比如将 abc 映射到 2，那么输入 b 需要按两下 2，输入 c 需要按三下 2。给定一个单词 word，返回输入该字符所需的最少按键次数。

与 3014.输入单词需要的最少按键次数I 相比，本题并没有说 word 是由不同字母组成。

将字母出现频次从大到小排序，大的优先分配在按键的第一个位置（按一下），然后是第二个位置（按两下），以此类推。

代码


/**
 * @date 2026-07-31 9:02
 */
public class MinimumPushes3016 {

    public int minimumPushes(String word) {
        int[] cnt = new int[26];
        for (char c : word.toCharArray()) {
            cnt[c - 'a']++;
        }
        PriorityQueue<int[]> q = new PriorityQueue<>((a, b) -> b[1] - a[1]);
        for (int i = 0; i < 26; i++) {
            q.offer(new int[]{i, cnt[i]});
        }
        int k = 0;
        int res = 0;
        for (int i = 0; i < 26; i++) {
            int[] e = q.poll();
            if (e[1] == 0) {
                break;
            }
            res += (k++ / 8 + 1) * e[1];
        }
        return res;
    }
}

性能

3014.输入单词需要的最少按键次数I

目标

给你一个字符串 word，由不同小写英文字母组成。

返回重新映射按键后输入 word 所需的最少按键次数。

下面给出了一种电话键盘上字母到按键的映射作为示例。注意 1，*，# 和 0 不对应任何字母。

示例 1：

输入：word = "abcde"
输出：5
解释：图片中给出的重新映射方案的输入成本最小。
"a" -> 在按键 2 上按一次
"b" -> 在按键 3 上按一次
"c" -> 在按键 4 上按一次
"d" -> 在按键 5 上按一次
"e" -> 在按键 6 上按一次
总成本为 1 + 1 + 1 + 1 + 1 = 5 。
可以证明不存在其他成本更低的映射方案。

示例 2：

输入：word = "xycdefghij"
输出：12
解释：图片中给出的重新映射方案的输入成本最小。
"x" -> 在按键 2 上按一次
"y" -> 在按键 2 上按两次
"c" -> 在按键 3 上按一次
"d" -> 在按键 3 上按两次
"e" -> 在按键 4 上按一次
"f" -> 在按键 5 上按一次
"g" -> 在按键 6 上按一次
"h" -> 在按键 7 上按一次
"i" -> 在按键 8 上按一次
"j" -> 在按键 9 上按一次
总成本为 1 + 2 + 1 + 2 + 1 + 1 + 1 + 1 + 1 + 1 = 12 。
可以证明不存在其他成本更低的映射方案。

说明：

1 <= word.length <= 26
word 仅由小写英文字母组成。
word 中的所有字母互不相同。

思路

可以将 26 个字母映射到 2 ~ 9 按键上，比如将 abc 映射到 2，那么输入 b 需要按两下 2，输入 c 需要按三下 2。给定一个由 不同字母 组成的单词 word，返回输入该字符所需的最少按键次数。

字母出现的频次都是 1，先将所有按键的第一个位置填满，然后是第二个、第三个。

录入单词所需的按键次数为 8 * (1 + 2 + …… + k) + (n % 8) * (k + 1) = 8 * (1 + k) * k / 2 + (n % 8) * (k + 1) = 4 * k * (k + 1) + (n % 8) * (k + 1) = (4 * k + n % 8) * (k + 1)。

代码


/**
 * @date 2026-07-30 9:10
 */
public class MinimumPushes3014 {

    public int minimumPushes_v1(String word) {
        int n = word.length();
        int k = n / 8;
        return (4 * k + n % 8) * (k + 1);
    }
}

性能

3517.最小回文排列I

目标

给你一个回文字符串 s。

返回 s 的按字典序排列的最小回文排列。

如果一个字符串从前往后和从后往前读都相同，那么这个字符串是一个回文字符串。

排列是字符串中所有字符的重排。

如果字符串 a 按字典序小于字符串 b，则表示在第一个不同的位置，a 中的字符比 b 中的对应字符在字母表中更靠前。

如果在前 min(a.length, b.length) 个字符中没有区别，则较短的字符串按字典序更小。

示例 1：

输入： s = "z"
输出： "z"
解释：
仅由一个字符组成的字符串已经是按字典序最小的回文。

示例 2：

输入： s = "babab"
输出： "abbba"
解释：
通过重排 "babab" → "abbba"，可以得到按字典序最小的回文。

示例 3：

输入： s = "daccad"
输出： "acddca"
解释：
通过重排 "daccad" → "acddca"，可以得到按字典序最小的回文。

说明：

1 <= s.length <= 10^5
s 由小写英文字母组成。
保证 s 是回文字符串。

思路

有一个回文字符串 s，将其重新排列成回文字符串，使得字典序最小。

记录字符串中字符的出现次数，然后按字典序从两边向中间填充，如果出现次数为奇数，那么该字符为中间元素。

代码


/**
 * @date 2026-07-28 9:03
 */
public class SmallestPalindrome3517 {

    public String smallestPalindrome(String s) {
        int[] cnt = new int[26];
        int n = s.length();
        char[] res = new char[n];
        for (char c : s.toCharArray()) {
            cnt[c - 'a']++;
        }
        char mid = 0;
        int cur = 0;
        for (int i = 0; i < 26; i++) {
            if (cnt[i] % 2 == 1) {
                mid = (char) ('a' + i);
            }
            int k = cnt[i] / 2;
            char c = (char) ('a' + i);
            for (int j = 0; j < k; j++) {
                res[cur + j] = c;
                res[n - cur - j - 1] = c;
            }
            cur += k;
        }
        if (n % 2 == 1) {
            res[n / 2] = mid;
        }
        return new String(res);
    }

}

性能

1464.数组中两元素的最大乘积

目标

给你一个整数数组 nums，请你选择数组的两个不同下标 i 和 j，使 (nums[i]-1)*(nums[j]-1) 取得最大值。

请你计算并返回该式的最大值。

示例 1：

输入：nums = [3,4,5,2]
输出：12 
解释：如果选择下标 i=1 和 j=2（下标从 0 开始），则可以获得最大值，(nums[1]-1)*(nums[2]-1) = (4-1)*(5-1) = 3*4 = 12 。

示例 2：

输入：nums = [1,5,4,5]
输出：16
解释：选择下标 i=1 和 j=3（下标从 0 开始），则可以获得最大值 (5-1)*(5-1) = 16 。

示例 3：

输入：nums = [3,7]
输出：12

说明：

2 <= nums.length <= 500
1 <= nums[i] <= 10^3

思路

从数组中取两个不同下标的元素相乘并返回最大的乘积。

找到数组最大的两个元素相乘即可。

代码


/**
 * @date 2026-07-27 8:55
 */
public class MaxProduct1464 {

    public int maxProduct(int[] nums) {
        Arrays.sort(nums);
        int n = nums.length;
        return (nums[n - 1] - 1) * (nums[n - 2] - 1);
    }
}

性能

628.三个数的最大乘积

目标

给你一个整型数组 nums ，在数组中找出由三个数组成的最大乘积，并输出这个乘积。

示例 1：

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

示例 2：

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

示例 3：

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

说明：

3 <= nums.length <= 10^4
-1000 <= nums[i] <= 1000

思路

从数组中取三个不同的下标，返回其乘积的最大值。

由于存在负数，分情况讨论，定义 max1、max2、max3 分别为前三大元素，min1、min2 分别是前二小元素：

如果 max1 < 0, 乘积只能为负，要使乘积最大，那么其绝对值应该最小，因此取 max1 * max2 * max3
如果 max2 < 0, 最大乘积可以为正，取最小的两个负数相乘，乘积最大，取 max1 * min1 * min2
如果 max3 < 0，乘积可能为正也可能为负（只有三个元素），不论那种情况，都可取 max1 * min1 * min2
如果 max3 > 0, 最大值可能是 max1 * max2 * max3 或者 max1 * min1 * min2

代码


/**
 * @date 2026-07-27 16:37
 */
public class MaximumProduct628 {

    public int maximumProduct_v1(int[] nums) {
        int max1 = -1001, max2 = -1001, max3 = -1001;
        int min1 = 1001, min2 = 1001;
        for (int num : nums) {
            if (num > max1) {
                max3 = max2;
                max2 = max1;
                max1 = num;
            } else if (num > max2) {
                max3 = max2;
                max2 = num;
            } else if (num > max3) {
                max3 = num;
            }
            if (num < min1) {
                min2 = min1;
                min1 = num;
            } else if (num < min2) {
                min2 = num;
            }
        }
        return Math.max(max1 * max2 * max3, max1 * min1 * min2);
    }

}

2026 年 8 月
一	二	三	四	五	六	日
					1	2
3	4	5	6	7	8	9
10	11	12	13	14	15	16
17	18	19	20	21	22	23
24	25	26	27	28	29	30
31