主題

LeetCode - 1299. Replace Elements with Greatest Element on Right Side 解題心得

Not In My Back Yard | 2021-05-06 00:00:12 | 巴幣 0 | 人氣 35

題目連結:


題目意譯:
給定一陣列 arr,替換掉其中每個元素為位於該元素右側的最大元素,並將最後一個元素替換為 -1。

經過以上程序後,回傳該陣列。

限制:
1 ≦ arr.length ≦ 10 ^ 4
1 ≦ arr[i] ≦ 10 ^ 5



範例測資:
範例 1:
輸入: arr = [17,18,5,4,6,1]
輸出: [18,6,6,6,1,-1]
解釋:
- 索引值 0 --> 在索引值 0 右側的最大元素位於索引值 1(18)。
- 索引值 1 --> 在索引值 1 右側的最大元素位於索引值 4(6)。
- 索引值 2 --> 在索引值 2 右側的最大元素位於索引值 4(6)。
- 索引值 3 --> 在索引值 3 右側的最大元素位於索引值 4(6)。
- 索引值 4 --> 在索引值 4 右側的最大元素位於索引值 5(1)。
- 索引值 5 --> 在索引值 5 右側沒有任何元素,所以我們放了一個 -1。

範例 2:
輸入: arr = [400]
輸出: [-1]
解釋: 在索引值 0 右側沒有任何元素。


解題思維:
因為每個元素都要替換成位於其右側的最大元素。那麼我們就從陣列的右側開始掃到左側,期間利用一個變數 M(初始化為 -1),代表當前掃到部分中最大的數字。

因為 M 的初始值為 -1,所以對於最右側的元素即是所求替換值。而當我們掃到 nums[i] 的時候(i < nums.length - 1),代表我們已經掃完了 i + 1 ~ nums.length - 1 之位置,而這剛好就是 nums[i] 的右側。因此此時的 M 值即是所求替換值。

因此我們掃完之後,便可以將所有元素替換成功。




此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

更多創作