本文共 2020 字，大约阅读时间需要 6 分钟。

一、母题

1.

延伸：既然可以求第三大的数，就可以求第n大或第n小的数。(原则上，n$\in [1,3]$)。

如果n > 3, 那么采用TreeSet来解题。以第4大的数为例子：

TreeSet
   
     ts = new TreeSet<>();for(int num : nums) {
   	ts.add(num);	if(ts.size() > 4) ts.remove(ts.first());}return ts.size() < 4 ? ts.last() : ts.first();
   

2.通解

class Solution {
       public int thirdMax(int[] nums) {
           long max1 = Long.MIN_VALUE, max2 = Long.MIN_VALUE, max3 = Long.MIN_VALUE;        for(int num : nums) {
               if(num == max1 || num == max2 || num == max3)                continue;            if(num > max1) {
                   max3 = max2;                max2 = max1;                max1 = num;            }            else if(num > max2) {
                   max3 = max2;                max2 = num;            }            else if(num > max3) {
                   max3 = num;            }        }        return max3 == Long.MIN_VALUE ? (int)max1 : (int)max3;           }}

核心思路：求第n大/小的数，就定义n个变量来存储。

比如：要求第3大的数，那么就用max1，max2，max3分别来存储第1、2、3大的数。

本题的坑点：

①nums[i]最小值可以是Integer.MIN_VALUE，所以max1~max3的类型为long;

②过滤掉重复数；

二、变体

1.

所以，本题的实质是遍历数组寻找3个最大的数和2个最小的数。（允许重复）

• AC代码

class Solution {
       public int maximumProduct(int[] nums) {
           int max1 = Integer.MIN_VALUE, max2 = Integer.MIN_VALUE, max3 = Integer.MIN_VALUE;        int min1 = Integer.MAX_VALUE, min2 = Integer.MAX_VALUE;        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, min1 * min2 * max1);    }}

转载地址：http://lxhhz.baihongyu.com/