Intuition#

核心思路：一次遍歷，若 index 為奇數時 nums[i] < nums[i-1]，或 index 為偶數時 nums[i] > nums[i-1]，就交換相鄰兩元素。

• 奇數位應該是局部最大（nums[i] >= nums[i-1]）
• 偶數位應該是局部最小（nums[i] <= nums[i-1]）
• 若不滿足就交換，交換不會破壞前面的 wiggle 性質

Approaches#

1: Sort Then Swap#

• 概念: 先排序，然後每兩個元素一組交換（swap nums[1] 和 nums[2]，swap nums[3] 和 nums[4]…）
• 時間複雜度: O(n log n) - 排序主導
• 空間複雜度: O(1) - 原地排序後原地交換

class Solution {
    fun wiggleSort(nums: IntArray) {
        nums.sort()
        for (i in 1 until nums.size - 1 step 2) {
            val temp = nums[i]
            nums[i] = nums[i + 1]
            nums[i + 1] = temp
        }
    }
}

⭐2: One-Pass Greedy Swap#

• 概念: 遍歷陣列，根據當前 index 的奇偶性判斷是否需要交換相鄰元素
• 時間複雜度: O(n) - 一次遍歷
• 空間複雜度: O(1) - 原地操作

class Solution {
    fun wiggleSort(nums: IntArray) {
        for (i in 1 until nums.size) {
            if ((i % 2 == 1 && nums[i] < nums[i - 1]) ||
                (i % 2 == 0 && nums[i] > nums[i - 1])) {
                val temp = nums[i]
                nums[i] = nums[i - 1]
                nums[i - 1] = temp
            }
        }
    }
}

為什麼交換不會破壞前面已建立的 wiggle 性質？以奇數位為例：若 nums[i] < nums[i-1]，交換後 nums[i-1] 變更小，而偶數位 i-1 本就要求較小值，所以 i-2 到 i-1 的關係不會被破壞。

🔑 Takeaways#

• Pattern: Wiggle / 交替排序 -> 局部性質的 Greedy 交換
• 關鍵技巧: 只看相鄰兩元素的局部關係，O(n) 一次遍歷解決問題。注意 Wiggle Sort II（324 題）要求嚴格不等式，解法不同且更難