# Leetcode nextGreaterElement

2019-06-20 11:06
##### Guaz
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.

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

Linux Mint
Arduino / Python 3.5.2
edytowany 9x, ostatnio: Guaz, 2019-06-20 11:37

Pozostało 580 znaków

2019-06-20 11:38
##### Mózg
1

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

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

edytowany 1x, ostatnio: Mózg, 2019-06-20 12:10

Pozostało 580 znaków

2019-06-20 11:50
##### lion137
1
1. Bo `6` jest pierwszym najwiekszym.
2. Bo znowu `2` jest pierwszym najwiekszym.
Zgodnie z konstrukcja struktury.

Pozostało 580 znaków

2019-06-20 12:13
##### Pyxis

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``````
edytowany 1x, ostatnio: Pyxis, 2019-06-20 12:14

Pozostało 580 znaków

2019-06-20 12:54
##### Guaz
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 :)

Linux Mint
Arduino / Python 3.5.2
edytowany 3x, ostatnio: Guaz, 2019-06-20 12:59

Pozostało 580 znaków

2019-06-25 12:54
##### Mózg
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``````

Pozostało 580 znaków

Liczba odpowiedzi na stronę