LeetCode 解題練習：Largest Number At Least Twice of Others

題目原文描述 https://leetcode.com/problems/largest-number-at-least-twice-of-others/

這一題主要觀念：

陣列走訪（Array Traversal）
最大值搜尋（Maximum Search）
一次掃描技巧（One Pass）
空間最佳化（Space Optimization）

屬於 LeetCode 的經典陣列入門題目。

中文描述：給定一個整數陣列 nums，保證陣列中存在唯一最大值。請判斷這個最大值是否至少是其他所有元素的兩倍。若是，則回傳該最大值在陣列中的索引；若否，則回傳 -1。

範例一：

Python

輸入: nums = [1, 2, 3, 6, 2, 3, 1]
輸出: 3

解釋：最大值是 6（位於索引 3），其他元素為 1,2,3,2,3,1，其中最大的其他元素是 3，6 >= 2*3，滿足條件。

範例二：

Python

輸入: nums = [1, 2, 3, 4, 6]
輸出: -1

解釋：最大值是 6，但存在 4，6 < 2*4，不滿足條件。

關鍵特性：

最大值唯一（不會有兩個相同最大值）。
陣列長度至少為 1。
元素可能包含 0 或負數（但最大值仍是唯一最大的）。

解法一：Two Pass（兩次遍歷）

這個解法的直覺是「分兩步走」：先找出老大是誰，再回頭檢查老大有沒有比其他人大兩倍。

核心思路：

第一次遍歷：找出最大值 largestNum 及其索引 largestIdx。
第二次遍歷：檢查陣列中每個非最大值的元素，是否滿足 largestNum >= 2 * n。只要有一個元素不滿足，就立刻返回 -1。
如果順利走完第二次都沒有被淘汰，說明最大值符合條件，回傳 largestIdx。

Python Code

class Solution:
    def dominantIndex(self, nums: List[int]) -> int:
        largestNum = -1 # 最大值
        largestIdx = -1 # 最大值位置
        
        # 找最大值與索引位置
        for i in range(len(nums)):
            if nums[i] > largestNum:
                largestNum = nums[i]
                largestIdx = i
        
        for n in nums:
            if n != largestNum and 2*n > largestNum: # 非最大值元素的兩倍是否大於最大值
                return -1
        
        return largestIdx

複雜度分析：

時間複雜度： $O(N)$ 。雖然走了兩次迴圈（ $2N$ 次運算），但在大 O 符號中常數忽略，依然是線性時間。
空間複雜度： $O(1)$ 。只用了幾個變數儲存最大值與索引，沒有額外佔用記憶體。

優缺點：

優點：思路非常直觀，容易理解，適合初學者。
缺點：需要兩次遍歷，時間複雜度為 O(n)（兩次線性掃描）。
空間複雜度：O(1)，只用了常數空間。

解法二：One Pass（單次遍歷）

這是進階的優化解法。我們不需要檢查「所有」元素，因為只要最大值大於或等於「第二大值」的兩倍，它就絕對大於其他更小元素的兩倍。

核心思路：在一次遍歷中同時記錄：

第一大值 largestNum 及其索引 largestIdx
第二大值 secondNum

當找到新的最大值時，把原本的最大值降級為第二大值。最後只需比較 largestNum >= 2 * secondNum 即可。

執行步驟

我們只走一趟迴圈，同時維護兩個變數：第一大（largestNum）與第二大（secondNum）。
當走訪到新元素 nums[i] 時，會有兩種情況需要更新：
- 情況 A：新元素比「第一大」還要大。這時，原本的第一大就退位變成「第二大」（secondNum = largestNum），而新元素變成新的第一大（largestNum = nums[i]）。
- 情況 B：新元素沒有比第一大，但比「第二大」還要大。這時只需要更新第二大（secondNum = nums[i]）。
巡訪完畢後，直接做一次終極二選一的判斷：if largestNum < 2 * secondNum，若是則回傳 -1，否則回傳第一大的索引。

Python Code

class Solution:
    def dominantIndex(self, nums: List[int]) -> int:
        largestNum = nums[0] # 最大值設定為第一個陣列元素
        secondNum = 0 # 第二大值
        largestIdx = 0 # 最大值位置
        
        # 找最大值與索引位置
        for i in range(1, len(nums)):
            if nums[i] > largestNum:
                secondNum = largestNum
                largestNum = nums[i]
                largestIdx = i
            elif nums[i] > secondNum:
                secondNum = nums[i]
        
        if largestNum < 2 * secondNum:
            return -1

        return largestIdx

重點說明：

當 nums[i] > largestNum 時，原本的 largestNum 就變成新的 secondNum。

elif 確保不會把最大值錯誤地更新到第二大。

對於只有一個元素的陣列（[5]），secondNum 保持為 0，5 >= 0，回傳 0，正確。
複雜度分析：
時間複雜度：$O(N)$。只走了一次迴圈，效率比解法一更高。
空間複雜度：$O(1)$。同樣只使用了固定的幾個變數。


常見錯誤錯誤一：排序後再找很多人會寫：
nums.sort()

雖然可行，但：
排序需要：O(n log n)
題目其實只需要：O(n)
效率較差。

錯誤二：忘記排除最大值錯誤：
if 2*n > largestNum:

會檢查到：6 × 2 > 6 永遠成立。

因此必須寫：if n != largestNum and 2*n > largestNum:

錯誤三：第二大值更新錯誤
錯誤：
largestNum = nums[i]
secondNum = largestNum

這樣：secondNum 會變成新的最大值。

正確順序：
secondNum = largestNum
largestNum = nums[i]


總結解法一 用「先找最大，再驗證」的思維，清晰易懂。
解法二 用「同時追蹤第一大與第二大」的方式，一次遍歷完成，效率更高。
這題主要考查陣列遍歷、維護極值的能力，是 LeetCode Easy 中很好的練習題。

邊界情況與注意事項陣列只有一個元素：[10] → 應回傳 0（沒有其他元素，條件自動成立）。
全部元素相同：不可能發生（題目保證最大值唯一）。
包含 0 或負數：如 [-1, 0, 5]，最大值 5 是其他元素的兩倍以上。
第二大值是 0：largestNum >= 0 一定成立。
最大值剛好兩倍：[3, 6] → 回傳 1（6 == 2*3）。
最大值小於兩倍：[4, 7] → 回傳 -1（7 < 8）。

 若您覺得文章寫得不錯，請點選文章上的廣告，來支持小編，謝謝。
If you like this post, please click the ads on the blog or buy me a coffee. Thank you very much.

搜尋此網誌