1019. Next Greater Node In Linked List

leetcode medium

#array#csharp#leetcode#linked-list#medium#search#stack

Task

Вам дана голова связного списка с n узлами. Для каждого узла в списке найдите значение следующего большего узла. То есть для каждого узла найдите значение первого узла, который находится рядом с ним и имеет строго большее значение, чем он. Верните целочисленный массив answer, где answer[i] - это значение следующего большего узла ith-узла (с индексацией по 1). Если у узла ith нет следующего большего узла, установите answer[i] = 0.

Пример:

Input: head = [2,1,5]

Output: [5,5,0]

C# solution

matched/original

public class ListNode {
    public int val;
    public ListNode next;
    public ListNode(int x) { val = x; }
}
public class Solution {
    public int[] NextLargerNodes(ListNode head) {
        var values = new List<int>();
        while (head != null) {
            values.Add(head.val);
            head = head.next;
        }
        
        var answer = new int[values.Count];
        var stack = new Stack<int>();
        
        for (int i = 0; i < values.Count; i++) {
            while (stack.Count > 0 && values[stack.Peek()] < values[i]) {
                answer[stack.Pop()] = values[i];
            }
            stack.Push(i);
        }
        
        return answer;
    }
}

C++ solution

auto-draft, review before submit

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
public class ListNode {
    public int val;
    public ListNode next;
    public ListNode(int x) { val = x; }
}
class Solution {
public:
    public vector<int>& NextLargerNodes(ListNode head) {
        var values = new List<int>();
        while (head != null) {
            values.push_back(head.val);
            head = head.next;
        }
        
        var answer = new int[values.size()];
        var stack = new stack<int>();
        
        for (int i = 0; i < values.size(); i++) {
            while (stack.size() > 0 && values[stack.Peek()] < values[i]) {
                answer[stack.pop()] = values[i];
            }
            stack.push(i);
        }
        
        return answer;
    }
}

Java solution

auto-draft, review before submit

import java.util.*;
import java.math.*;

// Auto-generated Java draft from the C# solution. Review API differences before LeetCode submit.
public class ListNode {
    public int val;
    public ListNode next;
    public ListNode(int x) { val = x; }
}
public class Solution {
    public int[] NextLargerNodes(ListNode head) {
        var values = new List<int>();
        while (head != null) {
            values.add(head.val);
            head = head.next;
        }
        
        var answer = new int[values.size()];
        var stack = new Stack<int>();
        
        for (int i = 0; i < values.size(); i++) {
            while (stack.size() > 0 && values[stack.peek()] < values[i]) {
                answer[stack.pop()] = values[i];
            }
            stack.push(i);
        }
        
        return answer;
    }
}

JavaScript solution

matched/original

class ListNode {
    constructor(val = 0, next = null) {
        this.val = val;
        this.next = next;
    }
}

class Solution {
    nextLargerNodes(head) {
        const values = [];
        while (head) {
            values.push(head.val);
            head = head.next;
        }
        
        const answer = Array(values.length).fill(0);
        const stack = [];
        
        for (let i = 0; i < values.length; i++) {
            while (stack.length && values[stack[stack.length - 1]] < values[i]) {
                answer[stack.pop()] = values[i];
            }
            stack.push(i);
        }
        
        return answer;
    }
}

Python solution

matched/original

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

class Solution:
    def nextLargerNodes(self, head: ListNode) -> List[int]:
        values = []
        while head:
            values.append(head.val)
            head = head.next
        
        answer = [0] * len(values)
        stack = []
        
        for i, value in enumerate(values):
            while stack and values[stack[-1]] < value:
                answer[stack.pop()] = value
            stack.append(i)
        
        return answer

Go solution

matched/original

type ListNode struct {
    Val  int
    Next *ListNode
}

func nextLargerNodes(head *ListNode) []int {
    var values []int
    for head != nil {
        values = append(values, head.Val)
        head = head.Next
    }
    
    answer := make([]int, len(values))
    stack := []int{}
    
    for i, value := range values {
        for len(stack) > 0 && values[stack[len(stack)-1]] < value {
            answer[stack[len(stack)-1]] = value
            stack = stack[:len(stack)-1]
        }
        stack = append(stack, i)
    }
    
    return answer
}

Explanation

Algorithm

Инициализация переменных:

Пройдитесь по всему списку и сохраните значения узлов в массив.

Инициализируйте стек для хранения индексов узлов, которые нужно обработать.

Поиск следующего большего элемента:

Итерируйте по массиву значений узлов.

Для каждого элемента, пока стек не пуст и текущий элемент больше, чем элемент на вершине стека, обновите массив ответов значением текущего элемента и удалите элемент из стека.

Добавьте текущий индекс в стек.

Заполнение оставшихся значений:

Для всех индексов, оставшихся в стеке, установите значение ответа равным 0, так как для них не найдено большего элемента.

😎