[LeetCode] 503. Next Greater Element II

오랜만에 풀어보는 알고리즘

- Problem

503. Next Greater Element II

Given a circular integer array nums (i.e., the next element of nums[nums.length - 1] is nums[0]), return the next greater number for every element in nums.

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, return -1 for this number.

Example 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.

Example 2:

Input: nums = [1,2,3,4,3]
Output: [2,3,4,-1,4]

Constraints:

• 1 <= nums.length <= 10^4
• -10^9 <= nums[i] <= 10^9

---

정수 배열 nums가 주어지고, nums는 환형 구조를 갖는다고 가정한다.
배열의 길이가 10 이라고 가정할 때, nums[10]은 nums[0], nums[11] = nums[1] 라고 볼 수 있다.

배열 nums의 원소를 num이라고 할 때, num 다음으로 큰 숫자를 찾아 배열로 반환한다.

예를 들어 배열 nums = [5, 1, 1]이 주어질 때, 차례대로 순회하면 다음과 같다.

• nums[0] = 5, 5보다 큰 숫자는 없다. 따라서 -1이 된다.
• nums[1] = 1 1 다음으로 오는 큰 숫자는 5다.
• nums[2] = 1 1 다음으로 오는 큰 숫자는 5다.

따라서 [-1, 5, 5]를 리턴해야 한다,

---

- 내 풀이

class Solution:
    def nextGreaterElements(self, nums: List[int]) -> List[int]:
        N = len(nums)
        stk = []
        answer = [-1] * N
        
        for _ in range(2):
            for i, v in enumerate(nums):
                while stk and stk[-1][1] < v:
                    answer[stk.pop()[0]] = v
                stk.append([i, v])

        return answer

---

- 결과