Leetcode nextGreaterElement

0

Hej, wstając rano z reguły staram się zrobić sobie jedno zadanie na codewars lub leetcode, dziś wyjątkowo mam problem ze zrozumieniem logiki zadania na leetcode :)

Given a circular array (the next element of the last element is the first element of the array), print the Next Greater Number for every element. The Next Greater Number of a number x is the first greater number to its traversing-order next in the array, which means you could search circularly to find its next greater number. If it doesn't exist, output -1 for this number.

Example 1:

Input: [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.

Note: The length of given array won't exceed 10000.

Ogólnie moje rozwiązanie wygląda póki co następująco:

class Solution(object):
    def nextGreaterElement(self, nums):
        next_greater = {}
        n = len(nums)
        out = [-1]*n
        
        for x, y, idx in zip(nums, (nums[1:]+[nums[0]]), range(n)):
            if y > x:
                next_greater[x] = y
            elif y-x:
                next_greater[y] = x
            z = nums[idx]
            while z in next_greater:
                z = next_greater.get(z)
            if z != nums[idx]:
                out[idx] = z
        
        return out

def test(inp, expected, out):
    if out != expected:
        print("FAILED")
        print("For input: {} | Output should be: {} not {}".format(inp, expected, out))
    else:
        print("PASS for {}".format(inp))

s = Solution()

test([1,2,1], [2,-1,2], s.nextGreaterElement([1,2,1])) #[2, -1, 2]
test([1,2,3,4,3], [2,3,4,-1,4], s.nextGreaterElement([1,2,3,4,3])) #[2, 3, 4, -1, 4]
test([5,4,3,2,1], [-1,5,5,5,5], s.nextGreaterElement([5,4,3,2,1])) #[-1, 5, 5, 5, 5]
test([1,5,3,6,8], [5,6,6,8,-1], s.nextGreaterElement([1,5,3,6,8])) #[5, -1, 6, 8, -1]
test([1,2,3,2,1], [2,3,-1,3,2], s.nextGreaterElement([1,2,3,2,1])) #[2, 3, -1, 3, 3]
#@Edit I jeszcze jeden nie działający po przeróbkach :)
test([100,1,11,1,120,111,123,1,-1,-100], [120,11,120,120,123,123,-1,100,100,100], \
s.nextGreaterElement([100,1,11,1,120,111,123,1,-1,-100])) 


Jednak nie mogę załapać dlaczego w przedostatnim przykładzie na drugiej pozycji zamiast -1 powinno być 6 :)
Oraz 2 na ostatniej pozycji zamiast 3 w ostatnim przykładzie.

Link do leetcode: https://leetcode.com/problems/next-greater-element-ii/

Jakieś pomysły co dokładniej źle rozumiem?

1

5 musisz porównać do [3,6,8,1]. 6 jest pierwszym większym elementem.

Optymalne rozwiązanie jest O(n). Hint: stos.

1
  1. Bo 6 jest pierwszym najwiekszym.
  2. Bo znowu 2 jest pierwszym najwiekszym.
    Zgodnie z konstrukcja struktury.
1

Weźmy listę [1, 5, 3, 6, 8]:

  • Na pierwszą pozycję gdzie jest 1, trafi 5, bo 5 > 1
  • Na drugą pozycję gdzie jest 5, trafi 6, bo 6 > 5
  • Na trzecią pozycję gdzie jest 3, trafi ponownie 6, bo 6 > 3
  • Na czwartą pozycję gdzie jest 6, trafi 8, bo 8 > 6
  • Na piątą pozycję gdzie jest 8, trafi ** -1**, bo jest to maksimum

Ostatecznie więc lista [1, 5, 3, 6, 8] zostanie przetransformowana do [5, 6, 6, 8, -1]. W przypadku listy [1, 2, 3, 2, 1] mamy:

  • Na pierwszą pozycję gdzie jest 1, trafi 2, bo 2 > 1
  • Na drugą pozycję gdzie jest 2, trafi 3, bo 3 > 2
  • Na trzecią pozycję gdzie jest 3, trafi -1, bo jest to maksimum
  • Na czwartą pozycję gdzie jest 2, trafi 3, bo 3 > 2
  • Na piątą pozycję gdzie jest 1, trafi 2, bo 2 > 1

Ostatecznie więc lista [1, 2, 3, 2, 1] zostanie przetransformowana do [2, 3, -1, 3, 2]. Przykładowe rozwiązanie:

class Solution(object):
    def nextGreaterElements(self, nums):

        stack = []
        size = len(nums)
        ans = [-1] * size
        for x in range(size * 2):
            i = x % size
            while stack and nums[stack[-1]] < nums[i]:
                ans[stack.pop()] = nums[i]
            stack.append(i)
        return ans
0

Dzięki za pomoc :). Całkowicie źle się do tego zabrałem próbując w ten naiwny sposób:


class Solution(object):
    def nextGreaterElement(self, nums):
        if nums:
            n = len(nums)
            out = [-1]*n
            max_num = max(nums)
        else:
            return []
        
        for i in range(n):
            if nums[i] == max_num:
                continue
            out[i] = self.get_next_greater(nums[i], (x for x in nums[i+1:n]), (x for x in nums[0:i]))
        return out
        
    def get_next_greater(self, elem, it1, it2):
        for item in it1:
            if elem < item:
                return item
        for item in it2:
            if elem < item:
                return item

Nie przeszło próby czasu, natomiast rozwiązanie kolegi @Pyxis już tak.
Niestety ciężko tu powiedzieć żebym dał radę temu 'code challenge' , ale przynajmniej zrozumiałem i umiem coś nowego, dzięki wszystkim za pomoc :)

Iterowałem w sumie dziesiątki razy po tym samym, przeoczając poradę od @Mózg do zastosowania stosu :)

0

Nie przeszło próby czasu

O(n^2) w limicie:

class Solution:
    def nextGreaterElements(self, xs):
        ys = collections.deque(xs)
        zs = []
        for x in xs:
            ys.rotate(-1)
            for y in ys:
                if y > x:
                    zs.append(y)
                    break
            else:
                zs.append(-1)
        return zs

1 użytkowników online, w tym zalogowanych: 0, gości: 1