503. Next Greater Element II

leetcode medium

#array#backtracking#csharp#leetcode#medium#search

Task

Дан циклический массив целых чисел nums (т.е. следующий элемент после nums[nums.length - 1] это nums[0]), верните следующее большее число для каждого элемента в nums.

Следующее большее число для числа x — это первое большее число, следующее за ним в порядке обхода массива, что означает, что вы можете искать циклически, чтобы найти следующее большее число. Если оно не существует, верните -1 для этого числа.

Пример:

Input: nums = [1,2,1]

Output: [2,-1,2]

Explanation: The first 1's next greater number is 2;

The number 2 can't find next greater number.

The second 1's next greater number needs to search circularly, which is also 2.

C# solution

matched/original

public class Solution {
    public int[] NextGreaterElements(int[] nums) {
        int n = nums.Length;
        int[] res = new int[n];
        Array.Fill(res, -1);
        
        for (int i = 0; i < n; i++) {
            for (int j = 1; j < n; j++) {
                if (nums[(i + j) % n] > nums[i]) {
                    res[i] = nums[(i + j) % n];
                    break;
                }
            }
        }
        
        return res;
    }
}

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.
class Solution {
public:
    public vector<int>& NextGreaterElements(vector<int>& nums) {
        int n = nums.size();
        vector<int>& res = new int[n];
        Array.Fill(res, -1);
        
        for (int i = 0; i < n; i++) {
            for (int j = 1; j < n; j++) {
                if (nums[(i + j) % n] > nums[i]) {
                    res[i] = nums[(i + j) % n];
                    break;
                }
            }
        }
        
        return res;
    }
}

Java solution

matched/original

public class Solution {
    public int[] nextGreaterElements(int[] nums) {
        int[] res = new int[nums.length];
        for (int i = 0; i < nums.length; i++) {
            res[i] = -1;
            for (int j = 1; j < nums.length; j++) {
                if (nums[(i + j) % nums.length] > nums[i]) {
                    res[i] = nums[(i + j) % nums.length];
                    break;
                }
            }
        }
        return res;
    }
}

JavaScript solution

matched/original

var nextGreaterElements = function(nums) {
    const n = nums.length;
    const res = Array(n).fill(-1);
    
    for (let i = 0; i < n; i++) {
        for (let j = 1; j < n; j++) {
            if (nums[(i + j) % n] > nums[i]) {
                res[i] = nums[(i + j) % n];
                break;
            }
        }
    }
    
    return res;
};

Python solution

matched/original

class Solution:
    def nextGreaterElements(self, nums: List[int]) -> List[int]:
        n = len(nums)
        res = [-1] * n
        
        for i in range(n):
            for j in range(1, n):
                if nums[(i + j) % n] > nums[i]:
                    res[i] = nums[(i + j) % n]
                    break
        
        return res

Go solution

matched/original

func nextGreaterElements(nums []int) []int {
    n := len(nums)
    res := make([]int, n)
    for i := range res {
        res[i] = -1
    }
    
    for i := 0; i < n; i++ {
        for j := 1; j < n; j++ {
            if nums[(i+j)%n] > nums[i] {
                res[i] = nums[(i+j)%n]
                break
            }
        }
    }
    
    return res
}

Explanation

Algorithm

Инициализация

Создайте массив res той же длины, что и nums, и заполните его значениями -1.

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

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

Возврат результата

Верните массив res.

😎