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?