go語言題解LeetCode1299將每個元素替換為右側最大元素
題目描述
1299. 將每個元素替換為右側最大元素 - 力扣(LeetCode)
給你一個數(shù)組 arr
,請你將每個元素用它右邊最大的元素替換,如果是最后一個元素,用 -1
替換。
完成所有替換操作后,請你返回這個數(shù)組。
示例 1:
輸入:arr = [17,18,5,4,6,1] 輸出:[18,6,6,6,1,-1] 解釋: - 下標 0 的元素 --> 右側最大元素是下標 1 的元素 (18) - 下標 1 的元素 --> 右側最大元素是下標 4 的元素 (6) - 下標 2 的元素 --> 右側最大元素是下標 4 的元素 (6) - 下標 3 的元素 --> 右側最大元素是下標 4 的元素 (6) - 下標 4 的元素 --> 右側最大元素是下標 5 的元素 (1) - 下標 5 的元素 --> 右側沒有其他元素,替換為 -1
示例 2:
輸入:arr = [400] 輸出:[-1] 解釋:下標 0 的元素右側沒有其他元素。
提示:
1 <= arr.length <= 10^4
1 <= arr[i] <= 10^5
思路分析
從題目可以看出
- 從右到左遍歷的話,剛好是從遍歷過的數(shù)中去尋找最大值。
- 從左到右遍歷的話,那么就需要提前比較還未遍歷的值。
不難看出從右到左遍歷只需要O(n)時間復雜度,
從左到右遍歷需要O(n^2)的時間復雜度
在這個題感悟到,其實有時候生活中遇到困難了,不妨換個思維去想一下
也許當前困難不過是對自己的一種考驗
多花點思維思考去解決比用簡單的惰性思維去“懶”解決要為后續(xù)實現(xiàn)的節(jié)省更多時間
AC 代碼
class Solution { public int[] replaceElements(int[] arr) { int max = -1; for (int i = arr.length - 1; i >= 0; i--) { int tmp = arr[i]; arr[i] = max; if (tmp > max) { max = tmp; } } return arr; } }
Java 百分百 - 將每個元素替換為右側最大元素
逆序遍歷罷了
代碼
class Solution { public int[] replaceElements(int[] arr) { int max = -1; int[] ans = new int[arr.length]; for(int i = arr.length-1;i >= 0;i--){ int temp = arr[i]; ans[i] = max; max = Math.max(max,temp); } return ans; } }
從右往左一次遍歷 - 將每個元素替換為右側最大元素
從右往左遍歷,先記錄右邊最大值 rightMax 為最后一個值,向左每次更新 rightMax,使用變量 t 先記住當前 arr[i] 就可以了。
class Solution { public int[] replaceElements(int[] arr) { int rightMax = arr[arr.length - 1]; arr[arr.length - 1] = -1; for (int i = arr.length - 2; i >= 0; i--) { int t = arr[i]; arr[i] = rightMax; if (t > rightMax) rightMax = t; } return arr; } }
以上就是go語言題解LeetCode1299將每個元素替換為右側最大元素的詳細內(nèi)容,更多關于go 元素替換右側最大元素的資料請關注腳本之家其它相關文章!