Java 陣列找第二大元素：單趟掃描雙變量法完整實作

O(n) 時間、O(1) 空間：面試必考的極值追蹤技巧

題目假設：陣列非空、元素為非負整數、全數互不相同。目標：單次遍歷找出第二大值。提供兩種邏輯等價但寫法不同的實作，並分析邊界處理。

演算法 1：動態維護 max/secMax，遇更大則交換

public static int getSecondMaxElem(int[] a) {
    if (a == null || a.length <= 1) return -1;
    int max = Math.max(a[0], a[1]);
    int secMax = a[0] + a[1] - max; // 另一個值
    for (int i = 2; i < a.length; i++) {
        int cur = a[i];
        if (cur > secMax) {
            secMax = cur;
            if (secMax > max) { // 同時更新 max
                int tmp = secMax; secMax = max; max = tmp;
            }
        }
    }
    return secMax;
}

演算法 2：分支明確的三區間判斷（推薦可讀性）

public static int getSecondMaxElem2(int[] a) {
    if (a == null || a.length <= 1) return -1;
    int max = Math.max(a[0], a[1]);
    int secMax = a[0] + a[1] - max;
    for (int i = 2; i < a.length; i++) {
        int cur = a[i];
        if (cur > max) {
            secMax = max; // 舊 max 降為第二大
            max = cur;
        } else if (cur > secMax) { // cur 在 (secMax, max] 區間
            secMax = cur;
        }
        // else cur <= secMax：無變化
    }
    return secMax;
}

測試用例與輸出

int[] arr = {2, 3, 1, 6, 7, 5, 9};
// 排序後：1,2,3,5,6,7,9 → 第二大 = 7
System.out.println("算法1：" + getSecondMaxElem(arr));  // 7
System.out.println("算法2：" + getSecondMaxElem2(arr)); // 7

擴展討論

• 含重複值：若允許重複，「第二大」定義需澄清（去重後第二大 vs 允許重複的第二大）。去重可先用 Set 或排序後跳過相等值。
• 泛型化：改用 Comparator<T> 適用任意可比較物件。
• 第 K 大：推廣至 Top-K 問題，可用 最小堆（大小 K） O(n log K) 或 快選演算法 平均 O(n)。
• 串流處理：資料量超記憶體時，維護固定大小的最小堆即可單趟解決。

常見錯誤

1. 初始化 max=Integer.MIN_VALUE, secMax=Integer.MIN_VALUE 會導致全負數陣列錯誤（題目限非負整數故未現形）。
2. 未處理長度 < 2 的邊界，拋 ArrayIndexOutOfBoundsException。
3. 邏輯分支漏掉 cur == max 或 cur == secMax（本題互不相同故安全，實務需考慮）。