1299. Replace Elements with Greatest Element on Right Side

LeetCode の挑戦ログ

Problem

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

• 配列の右側で最大の値に置き換えた配列を作成する
• 配列の最後に -1 をつける

Solution

class Solution {
    public int[] replaceElements(int[] arr) {
        List<Integer> nums = Arrays.stream(arr).boxed().collect(Collectors.toUnmodifiableList());

        int[] replaced = new int[nums.size()];
        int max = extractMax(nums.subList(1, nums.size()));
        for (int i = 0; i < (nums.size() - 1); i++) {
            if (nums.get(i) == max) {
                max = extractMax(nums.subList(i + 1, nums.size()));
            }
            replaced[i] = max;
        }
        // last element
        replaced[replaced.length - 1] = -1;

        return replaced;
    }

    private int extractMax(List<Integer> list) {
        return list.stream()
                .mapToInt(Integer::intValue)
                .max()
                .orElse(0);
    }
}

Impressions

• 最大値を毎回計算していたら Time Limit になってしまった
• 一度計算したら、その最大値が出てくるまでは計算不要にした