説明

単一リンク リスト node が与えられた場合、すべてのノードの値をその右側にある最初の大きなノードの値に置き換えます.ノードに次に大きいノードがない場合は、その値を 0 に設定します.

制約:

n ≤ 100,000 n は node のノード数です

例1

入力

node = [3, 2, 4, 5]

出力

[4, 4, 5, 0]

例2

入力

node = [1, 1, 1, 1]

出力

[0, 0, 0, 0]

直感

このリンクされたリストを逆にする

番号をスタックに格納します

ピークを現在のノード値と比較します

小さいか等しい場合は投げます

大きいか空の場合は、ノードの値をリセットします

実装

import java.util.*;

/**
 * class LLNode {
 *   int val;
 *   LLNode next;
 * }
 */
class Solution {
    public LLNode solve(LLNode node) {
        Stack<Integer> maxStack = new Stack<>();
        LLNode reverse = reverse(node);
        LLNode curr = reverse;
        while (curr != null) {
            if (maxStack.isEmpty()) {
                maxStack.push(curr.val);
                curr.val = 0;

            } else {
                while (!maxStack.isEmpty() && curr.val >= maxStack.peek()) {
                    maxStack.pop();
                }
                if (maxStack.isEmpty()) {
                    maxStack.push(curr.val);
                    curr.val = 0;
                } else {
                    int firstMax = maxStack.peek();
                    maxStack.push(curr.val);
                    curr.val = firstMax;
                }
            }
            curr = curr.next;
        }
        return reverse(reverse);
    }

    private LLNode reverse(LLNode node) {
        LLNode prev = null;
        LLNode curr = node;
        LLNode next;
        while (curr != null) {
            next = curr.next;
            curr.next = prev;
            prev = curr;
            curr = next;
        }
        return prev;
    }
}

時間の複雑さ

時間: O(n)

スペース: O(n)