[LeetCode] 1299. Replace Elements with Greatest Element on Right Side

[grandyang]

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

这道题给了一个数组 arr，说是让把每个数字更新为其右边的数字中最大的一个，最后一个数字变为 -1。既然是一道 Easy 的题目，就不用担心解法会太复杂，一般都是较短的行数就能搞定的。让求每个数字右边的数字中最大的一个，当然不能每次都遍历右边所有的数字来找最大值，虽说是 Easy 题目，但最好也别这么暴力地解，多少还是要给 OJ 一些尊重的。从左往右不好使的话，可以调个头，从右往左去更新，这样就简单的多了，最后一个数字直接更新为 -1，然后只要维护一个从右往左的当前最大值，每次用来更新右往左的对应位置即可，基本没什么难度，只要能想到换个方向更新，基本就迎刃而解了，参见代码如下：

class Solution {
public:
    vector<int> replaceElements(vector<int>& arr) {
        int n = arr.size(), curMax = INT_MIN;
        vector<int> res(n, -1);
        for (int i = n - 2; i >= 0; --i) {
            curMax = max(curMax, arr[i + 1]);
            res[i] = curMax;
        }
        return res;
    }
};

Github 同步地址:

#1299

类似题目：

Two Furthest Houses With Different Colors

参考资料：

https://leetcode.com/problems/replace-elements-with-greatest-element-on-right-side/

https://leetcode.com/problems/replace-elements-with-greatest-element-on-right-side/discuss/463249/JavaC%2B%2BPython-Straight-Forward

LeetCode All in One 题目讲解汇总(持续更新中...)

（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，快快加入吧～）

喜欢请点赞，疼爱请打赏❤️~.~

微信打赏

|

Venmo 打赏

---|---