설명

단일 연결 목록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)