LeetCode — Replace Elements with Greatest Element on Right Side C 语言 AC CODE

Given an array arr, replace every element in that array with the greatest element among the elements to its right, and replace the last element with -1.

After doing so, return the array.

Example 1:

Input: arr = [17,18,5,4,6,1]
Output: [18,6,6,6,1,-1]
Explanation:

• index 0 –> the greatest element to the right of index 0 is index 1 (18).
• index 1 –> the greatest element to the right of index 1 is index 4 (6).
• index 2 –> the greatest element to the right of index 2 is index 4 (6).
• index 3 –> the greatest element to the right of index 3 is index 4 (6).
• index 4 –> the greatest element to the right of index 4 is index 5 (1).
• index 5 –> there are no elements to the right of index 5, so we put -1.

Example 2:

Input: arr = [400]
Output: [-1]
Explanation: There are no elements to the right of index 0.

Constraints:

1 <= arr.length <= 104
1 <= arr[i] <= 105

自己想到的还是常规解法，两层For循环，简单省事。

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* replaceElements(int* arr, int arrSize, int* returnSize){
    
    for( int i = 0; i < arrSize - 1; i++){
        int rightMax = arr[ i + 1 ];
        
        for( int j = i + 1; j < arrSize; j++){
            if( arr[j] > rightMax ) rightMax = arr[j];
        }
        arr[i] = rightMax;
        
    }
    arr[arrSize - 1] = -1;
    
    *returnSize = arrSize;
    
    return arr;

}

其他人时间只要 O（N）的解法是直接一个循环过去，从最右边来计算最大值，逐个进行替换，然后直接一步到位，逻辑也不复杂，自己写一遍记录一下：

int* replaceElements(int* arr, int arrSize, int* returnSize){
    
    if( arrSize == 0  ) return arr;
    
    int max = arr[ arrSize - 1 ];
    
    for(int i = arrSize - 2; i >= 0;  i--){
        int tmp = arr[i];
        arr[i] = max;
        if( tmp > max) max = tmp;
    }
    
    arr[arrSize - 1] = -1;
    *returnSize = arrSize;
    
    return arr;

}