Description
給定陣列
arr，將每個元素替換為其右側所有元素中的最大值，最後一個元素替換為-1。
Example:
Input: arr = [17,18,5,4,6,1] Output: [18,6,6,6,1,-1]
Intuition#
核心思路：從右往左遍歷，維護一個「右側最大值」變數，邊走邊更新。
- 如果從左往右，每個位置都需要掃描右邊所有元素找最大值，O(n^2)
- 從右往左只需維護一個 running max，O(n) 即可完成
Approaches#
1: Brute Force#
- 概念: 對每個位置，掃描其右側所有元素找最大值
- 時間複雜度:
O(n^2)- 每個位置掃描右側 - 空間複雜度:
O(1)- 原地修改
class Solution {
fun replaceElements(arr: IntArray): IntArray {
val n = arr.size
val result = IntArray(n)
for (i in 0 until n - 1) {
var max = Int.MIN_VALUE
for (j in i + 1 until n) {
max = maxOf(max, arr[j])
}
result[i] = max
}
result[n - 1] = -1
return result
}
}⭐2: Reverse Traversal（從右往左）#
- 概念: 從最後一個元素開始，維護右側最大值
rightMax，邊遍歷邊更新 - 時間複雜度:
O(n)- 一次遍歷 - 空間複雜度:
O(1)- 原地修改
class Solution {
fun replaceElements(arr: IntArray): IntArray {
var rightMax = -1
for (i in arr.lastIndex downTo 0) {
val newMax = maxOf(rightMax, arr[i])
arr[i] = rightMax
rightMax = newMax
}
return arr
}
}🔑 Takeaways#
- Pattern: 逆序遍歷 + 維護累積值，是處理「右側資訊」的常見技巧
- 關鍵技巧: 遇到需要查詢「右側最大/最小」的題目，先想到從右往左掃描