题解 | 三个数的最大乘积

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 最大乘积
     * @param A int整型一维数组
     * @return long长整型
     */
    public long solve (int[] A) {
        // write code here
        //取出来三个数，求乘积最大，那肯定是三个正数，或者是两个负数加一个正数，可以使用大小顶堆
        //小顶堆，存放正数，从小到大排序，当遇到一个更大的数时，排出最小的元素
        PriorityQueue<Long> min = new PriorityQueue<Long>();
        //大顶堆，存放负数，操作和正数一致
        PriorityQueue<Long> max = new PriorityQueue<Long>((a,b) -> Long.compare(b,a));
        //强转为long类型，为了避免相乘溢出
        for(int num : A){
            Long n = (long)num;
            //维护最大的三个正数
            min.offer(n);
            if(min.size()>3)
            min.poll();
            //维护最小的两个负数
            max.offer(n);
            if(max.size()>2)
            max.poll();
        }
        //三个正数，依次是第三大，第二大，第一大
        Long max3 = min.poll();
        Long max2 = min.poll();
        Long max1 = min.poll();

        //两个负数
        Long min2 = max.poll();
        Long min1 = max.poll();
        return Math.max(max1 * max2 * max3, min1 * min2 * max1);
    }
}