628. 三个数的最大乘积

;(function () {
  /**
   * 628. 三个数的最大乘积
   * 给你一个整型数组 nums ，在数组中找出由三个数组成的最大乘积，并输出这个乘积。
   *
   * 输入：nums = [1,2,3]
   * 输出：6
   *
   * 输入：nums = [1,2,3,4]
   * 输出：24
   *
   * 输入：nums = [-1,-2,-3]
   * 输出：-6
   *
   */

  function maximumProduct(nums: number[]): number {
    // 方法一：排序
    // // 全正数：最大的三个数； 全负数：最大的三个数；有正数和负数：最小的两个负数（绝对值最大）和最大的正数。
    // nums.sort((a, b) => a - b);
    // const n = nums.length;
    // return Math.max(nums[n - 1] * nums[n - 2] * nums[n - 3], nums[0] * nums[1] * nums[n - 1])

    // 方法二：并查集
    let min1 = Number.MAX_SAFE_INTEGER,
      min2 = Number.MAX_SAFE_INTEGER
    let max1 = -Number.MAX_SAFE_INTEGER,
      max2 = -Number.MAX_SAFE_INTEGER,
      max3 = -Number.MAX_SAFE_INTEGER
    for (let x of nums) {
      if (x < min1) {
        min2 = min1
        min1 = x
      } else if (x < min2) {
        min2 = x
      }

      if (x > max1) {
        max3 = max2
        max2 = max1
        max1 = x
      } else if (x > max2) {
        max3 = max2
        max2 = x
      } else if (x > max3) {
        max3 = x
      }
    }
    return Math.max(max1 * max2 * max3, min1 * min2 * max1)
  }

  const nums = [1, 2, 3]
  const nums2 = [1, 2, 3, 4]
  const nums3 = [-1, -3, 2, -4]
  const nums4 = [-1, 3, 2, -4]
  console.log(maximumProduct(nums))
  console.log(maximumProduct(nums2))
  console.log(maximumProduct(nums3))
  console.log(maximumProduct(nums4))
})()