解題說明
Replace Elements with Greatest Element on Right Side
題目描述:
給定一個陣列 arr,將每個元素替換為其右邊所有元素中的最大值。最後一個元素替換為 -1。
解題思路:
從右往左遍歷陣列。維護一個變數 rightMax 記錄當前位置右邊的最大值(初始為 -1)。對每個位置,先保存原值,再將該位置替換為 rightMax,最後用原值更新 rightMax。這樣一次遍歷即可完成,不需要對每個元素都掃描右邊所有元素。
C++ 解法
複雜度分析
時間複雜度:O(n) — 單次從右到左遍歷。
空間複雜度:O(1) — 只使用一個額外變數(原地修改)。
虛擬碼
1. Set rightMax = -1 2. For i from arr.length - 1 down to 0: a. Save cur = arr[i] b. Set arr[i] = rightMax c. Update rightMax = max(rightMax, cur) 3. Return arr
其他解法
暴力法 O(n^2):對每個元素,掃描其右邊所有元素取最大值。簡單直觀但效率差。
後綴最大值陣列:先建立後綴最大值陣列 suffixMax[i] = max(arr[i+1..n-1]),再逐一替換。時間 O(n),但需要 O(n) 額外空間。不如從右往左遍歷的 O(1) 空間解法。
延伸思考
- 若要替換為右邊的最小值而非最大值,演算法需要什麼修改?
- 若要替換為右邊第 k 大的元素,時間複雜度會如何變化?
- 若要同時求左邊最大值和右邊最大值,如何在 O(n) 時間內完成?