go語言題解LeetCode1299將每個元素替換為右側(cè)最大元素

更新時(shí)間：2023年01月03日 10:35:19 作者：劉09k11

這篇文章主要為大家介紹了go語言LeetCode刷題1299將每個元素替換為右側(cè)最大元素示例詳解，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進(jìn)步，早日升職加薪

題目描述

1299. 將每個元素替換為右側(cè)最大元素 - 力扣（LeetCode）

給你一個數(shù)組 arr ，請你將每個元素用它右邊最大的元素替換，如果是最后一個元素，用 -1 替換。

完成所有替換操作后，請你返回這個數(shù)組。

示例 1：

輸入：arr = [17,18,5,4,6,1]
輸出：[18,6,6,6,1,-1]
解釋：
- 下標(biāo) 0 的元素 --> 右側(cè)最大元素是下標(biāo) 1 的元素 (18)
- 下標(biāo) 1 的元素 --> 右側(cè)最大元素是下標(biāo) 4 的元素 (6)
- 下標(biāo) 2 的元素 --> 右側(cè)最大元素是下標(biāo) 4 的元素 (6)
- 下標(biāo) 3 的元素 --> 右側(cè)最大元素是下標(biāo) 4 的元素 (6)
- 下標(biāo) 4 的元素 --> 右側(cè)最大元素是下標(biāo) 5 的元素 (1)
- 下標(biāo) 5 的元素 --> 右側(cè)沒有其他元素，替換為 -1

示例 2：

輸入：arr = [400]
輸出：[-1]
解釋：下標(biāo) 0 的元素右側(cè)沒有其他元素。

提示：

1 <= arr.length <= 10^4

1 <= arr[i] <= 10^5

思路分析

從題目可以看出

從右到左遍歷的話，剛好是從遍歷過的數(shù)中去尋找最大值。
從左到右遍歷的話，那么就需要提前比較還未遍歷的值。

不難看出從右到左遍歷只需要O(n)時(shí)間復(fù)雜度，

從左到右遍歷需要O(n^2)的時(shí)間復(fù)雜度

在這個題感悟到，其實(shí)有時(shí)候生活中遇到困難了，不妨換個思維去想一下

也許當(dāng)前困難不過是對自己的一種考驗(yàn)

多花點(diǎn)思維思考去解決比用簡單的惰性思維去“懶”解決要為后續(xù)實(shí)現(xiàn)的節(jié)省更多時(shí)間

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 百分百 - 將每個元素替換為右側(cè)最大元素

逆序遍歷罷了

代碼

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;
    }
}

從右往左一次遍歷 - 將每個元素替換為右側(cè)最大元素

從右往左遍歷，先記錄右邊最大值 rightMax 為最后一個值，向左每次更新 rightMax，使用變量 t 先記住當(dāng)前 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將每個元素替換為右側(cè)最大元素的詳細(xì)內(nèi)容，更多關(guān)于go 元素替換右側(cè)最大元素的資料請關(guān)注腳本之家其它相關(guān)文章！

您可能感興趣的文章: