題目描述:
給定一個陣列 arr,將每個元素替換為其右邊所有元素中的最大值。最後一個元素替換為 -1。
解題思路:
從右往左遍歷陣列。維護一個變數 rightMax 記錄當前位置右邊的最大值(初始為 -1)。對每個位置,先保存原值,再將該位置替換為 rightMax,最後用原值更新 rightMax。這樣一次遍歷即可完成,不需要對每個元素都掃描右邊所有元素。
時間複雜度: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) 空間解法。