本题一开始没有想明白,其实并不难,大概分析一下几种可能性:

    • 非负数的数量>=3:
      • 3个最大的非负数:628. Maximum Product of Three Numbers - 图1
      • 如果最小的两个数是负数,则可能是 628. Maximum Product of Three Numbers - 图2
    • 非负数的数量为2:
      • 只有3个数: 628. Maximum Product of Three Numbers - 图3
      • 比3个数多,则有2个或以上的负数,此时: 628. Maximum Product of Three Numbers - 图4
    • 非负数的数量为1:
      • 结果必然是 628. Maximum Product of Three Numbers - 图5
    • 非负数数量为0:
      • 结果必然是最大的三个负数: 628. Maximum Product of Three Numbers - 图6

    如上分析,只需要记录最大的3个数字: max1, max2, max3,以及最小的2个数字: min1, min2
    解法如下:

    1. class Solution {
    2. public int maximumProduct(int[] nums) {
    3. int max1 = Integer.MIN_VALUE;
    4. int max2 = Integer.MIN_VALUE;
    5. int max3 = Integer.MIN_VALUE;
    6. int min1 = Integer.MAX_VALUE;
    7. int min2 = Integer.MAX_VALUE;
    8. for (int num : nums) {
    9. if (num > max1) {
    10. max3 = max2;
    11. max2 = max1;
    12. max1 = num;
    13. }
    14. else if (num > max2) {
    15. max3 = max2;
    16. max2 = num;
    17. }
    18. else if (num > max3) {
    19. max3 = num;
    20. }
    21. if (num < min1) {
    22. min2 = min1;
    23. min1 = num;
    24. }
    25. else if (num < min2) {
    26. min2 = num;
    27. }
    28. }
    29. return Math.max(max1 * max2 * max3, max1 * min1 * min2);
    30. }
    31. }