leetcode
leetcode 551 ~ 600
三个数的最大乘积

三个数的最大乘积

难度:

标签:

题目描述

代码结果

运行时间: 35 ms, 内存: 16.9 MB


/*
 * 思路:
 * 1. 使用Java Stream对数组进行排序。
 * 2. 使用Stream相关操作找到三个最大的正数和两个最小的负数。
 * 3. 计算两种可能的最大乘积,返回其中的最大值。
 */
import java.util.Arrays;
import java.util.stream.IntStream;
 
public class Solution {
    public int maximumProduct(int[] nums) {
        // 排序后获取最大的三个数和最小的两个数
        int[] sorted = IntStream.of(nums).sorted().toArray();
        int n = sorted.length;
        // 计算两种可能的最大乘积
        int product1 = sorted[n - 1] * sorted[n - 2] * sorted[n - 3]; // 三个最大的正数
        int product2 = sorted[0] * sorted[1] * sorted[n - 1];         // 两个最小的负数和一个最大的正数
        // 返回最大值
        return Math.max(product1, product2);
    }
}
 

解释

方法:

该题解的思路是在数组中维护最大的三个数和最小的两个数。遍历数组,对于每个元素,检查它是否比当前最大的三个数中的任意一个更大,或者比当前最小的两个数中的任意一个更小。如果满足条件,就更新对应的最大数或最小数,并保持它们按照大小顺序排列。最后,返回最大的三个数的乘积与最大数与最小的两个数的乘积中的较大值。

时间复杂度:

O(n)

空间复杂度:

O(1)

代码细节讲解

🦆
如何确保在更新最大或最小值时,不会错误地覆盖掉其它重要的最大或最小值?
在更新最大或最小值时,代码通过使用条件判断和适当的排序方法来确保不会覆盖掉其它重要值。例如,当发现一个新的最大值时,不是简单地替换当前最大值,而是将新值放入适当位置,并将其他值按顺序下移。这种方法确保了在更新任一值时,其他重要的值仍被保存并适当地调整位置。
🦆
在更新最大的三个数或最小的两个数时,为什么选择在更新后排序,而不是在比较前就维护好序列顺序?
在比较前维护序列的顺序可能会导致更多的计算,因为每次插入新的值都可能需要比较和移动。而在更新后排序可以减少操作的次数,因为只有在值确实需要更新时才进行排序。这种方法提高了效率,尤其是在大多数情况下新遍历的值并不会成为新的最大或最小值时更为明显。
🦆
函数`sort_max`和`sort_min`中的比较和交换是否可能导致不必要的操作,即使数值没有发生改变?
是的,`sort_max`和`sort_min`函数中的比较和交换可能会导致不必要的操作。如果数值没有发生改变(即新插入的值并未改变排序后的序列),这些函数仍会执行比较和可能的交换操作。这可能导致额外的计算开销,尽管这种情况在大多数情况下对性能的影响较小。
🦆
当元素可能同时更新最大值和最小值数组时,如何处理这种情况以避免潜在的错误或遗漏?
在这种情况下,代码需要确保任何元素的更新都独立处理,并检查对最大值和最小值的潜在影响。例如,如果一个新元素可能是新的最小值也可能是新的最大值,代码首先在最小值数组进行更新和排序,然后再处理最大值数组。这种方法确保了更新的正确性和数据的完整性,避免了因处理顺序错误而导致的潜在遗漏。

相关问题

乘积最大子数组

给你一个整数数组 nums ,请你找出数组中乘积最大的非空连续子数组(该子数组中至少包含一个数字),并返回该子数组所对应的乘积。

测试用例的答案是一个 32-位 整数。

 

示例 1:

输入: nums = [2,3,-2,4]
输出: 6
解释: 子数组 [2,3] 有最大乘积 6。

示例 2:

输入: nums = [-2,0,-1]
输出: 0
解释: 结果不能为 2, 因为 [-2,-1] 不是子数组。

 

提示:

  • 1 <= nums.length <= 2 * 104
  • -10 <= nums[i] <= 10
  • nums 的任何前缀或后缀的乘积都 保证 是一个 32-位 整数