わたしの部屋

1
初始：max = null, second = null
2

3
遇到 3：max = 3
4
遇到 1：second = 1
5
遇到 5：second = 3, max = 5
6
遇到 2：不更新（2 < second = 3）
7
遇到 4：second = 4

1
class Solution {
2
    public int secondLargest(int[] nums) {
3
        if (nums == null || nums.length < 2) {
4
            throw new IllegalArgumentException("数组长度至少为 2");
5
        }
6

7
        Integer max = null;
8
        Integer second = null;
9

10
        for (int num : nums) {
11
            // 出现新的最大值：原来的 max 退为第二大
12
            if (max == null || num > max) {
13
                second = max;
14
                max = num;
15
            // num 必须严格小于 max，才能作为严格第二大的候选
16
            } else if (num < max && (second == null || num > second)) {
17
                second = num;
18
            }
19
        }
20

21
        // 如果没有找到不同于 max 的数，说明严格第二大不存在
22
        if (second == null) {
23
            throw new IllegalArgumentException("不存在严格第二大元素");
24
        }
25

26
        return second;
27
    }
28
}

1
class Solution {
2
    static class Pair {
3
        int max;
4
        Integer second;
5

6
        Pair(int max, Integer second) {
7
            this.max = max;
8
            this.second = second;
9
        }
10
    }
11

12
    public int secondLargest(int[] nums) {
13
        if (nums == null || nums.length < 2) {
14
            throw new IllegalArgumentException("数组长度至少为 2");
15
        }
16

17
        Pair ans = divide(nums, 0, nums.length - 1);
18

19
        if (ans.second == null) {
20
            throw new IllegalArgumentException("不存在严格第二大元素");
21
        }
22

23
        return ans.second;
24
    }
25

26
    private Pair divide(int[] nums, int left, int right) {
27
        // 单个元素区间：只有最大值，还不存在严格第二大
28
        if (left == right) {
29
            return new Pair(nums[left], null);
30
        }
31

32
        int mid = left + (right - left) / 2;
33

34
        // 分别求左右子数组的最大值和第二大值
35
        Pair leftPair = divide(nums, left, mid);
36
        Pair rightPair = divide(nums, mid + 1, right);
37

38
        // 合并左右子问题的结果
39
        return merge(leftPair, rightPair);
40
    }
41

42
    private Pair merge(Pair a, Pair b) {
43
        if (a.max > b.max) {
44
            // a 贡献全局最大值，第二大只能来自 a.second 或 b.max
45
            return new Pair(a.max, maxNullable(a.second, b.max));
46
        } else if (a.max < b.max) {
47
            // b 贡献全局最大值，第二大只能来自 a.max 或 b.second
48
            return new Pair(b.max, maxNullable(a.max, b.second));
49
        } else {
50
            // 两边最大值相同，不能把重复最大值当成严格第二大
51
            return new Pair(a.max, maxNullable(a.second, b.second));
52
        }
53
    }
54

55
    private Integer maxNullable(Integer a, Integer b) {
56
        // null 表示当前还没有严格第二大候选
57
        if (a == null) {
58
            return b;
59
        }
60
        if (b == null) {
61
            return a;
62
        }
63
        return Math.max(a, b);
64
    }
65
}

1
Pair leftPair = divide(nums, left, mid);
2
Pair rightPair = divide(nums, mid + 1, right);
3

4
return merge(leftPair, rightPair);