[LeetCode - Biweekly Contest 90]2454. Next Greater Element IV

2454. Next Greater Element IV

Hard

You are given a 0-indexed array of non-negative integers nums. For each integer in nums, you must find its respective second greater integer.

The second greater integer of nums[i] is nums[j] such that:

• j > i
• nums[j] > nums[i]
• There exists exactly one index k such that nums[k] > nums[i] and i < k < j.

If there is no such nums[j], the second greater integer is considered to be -1.

• For example, in the array [1, 2, 4, 3], the second greater integer of 1 is 4, 2 is 3, and that of 3 and 4 is -1.

Return an integer array answer, where answer[i] is the second greater integer of nums[i].

 

Example 1:

Input: nums = [2,4,0,9,6]
Output: [9,6,6,-1,-1]
Explanation:
0th index: 4 is the first integer greater than 2, and 9 is the second integer greater than 2, to the right of 2.
1st index: 9 is the first, and 6 is the second integer greater than 4, to the right of 4.
2nd index: 9 is the first, and 6 is the second integer greater than 0, to the right of 0.
3rd index: There is no integer greater than 9 to its right, so the second greater integer is considered to be -1.
4th index: There is no integer greater than 6 to its right, so the second greater integer is considered to be -1.
Thus, we return [9,6,6,-1,-1].

Example 2:

Input: nums = [3,3]
Output: [-1,-1]
Explanation:
We return [-1,-1] since neither integer has any integer greater than it.

 

Constraints:

• 1 <= nums.length <= 105
• 0 <= nums[i] <= 109

---

문제 풀이

• 배열이 하나가 주어진다. 
• 각 배열 값 위치에서 자기 자신의 숫자값보다 큰 숫자들을 찾아야한다.
• 그 숫자들은 자신 보다 오른쪽에 위치해야만하고, 각자의 크기는 상관 없지만 자기자신보다 오른쪽으로 두번째로 큰 숫자를 답으로 저장해야한다.
• 즉, [2, 4, 0, 9, 6]이 있다면 2보다 큰 숫자중에 오른쪽에서 두번째로 먼 숫자는 9이다. 
• 4가 첫번째로 크고 9가 두번째로 2보다 크다. 
• 제한을 보면 배열의 총길이의 최대 길이가 N^5 이다. O(NlogN)이하의 알고리즘을 사용해야한다.
• 힙과 스택을 사용하여 문제를 풀 수 있다. 
• 첫번째 스택은 자신 보다 큰 숫자가 한번 나오기 전까지 숫자를 보관해 놓는 장소이다.
• 두번째 힙은 배열에서 숫자의 위치를 오름차순으로 저장하되 자신의 오른쪽에 큰 숫자를 처음 발견했을때 숫자를 저장한다.
• 예시를 들어보면, [1, 3, 5, 8]이 있다고 가정하자.
• for 루프를 돌면서 1 숫자가 첫번째 스택에 들어가고, 
• 다음 과정에서 3과 비교하여 스택에 들어가있는 숫자보다 크다면 스택의 값을 뽑아서 힙에 - 값을 곱하여 넣는다.
• 그리고 방금 비교한 숫자도 스택에 들어간다.
• 그리고 다음 5를 비교할때 st1 에는 3이 들어가있고 st2에는 1이 들어가 있다. 
• 지금 숫자 5가 st2의 1보다 크기 때문에 1의 오른쪽에서 큰 숫자들중 두번째 숫자는 5가 된다. 
• 힙을 사용하지 않으면 발생하는 문제는 [3, 0, 3, 5] 배열을 봤을때 오른쪽에 작은 숫자가 있을때
• s2에 3, 0가 들어가 있다면 5의 차례가 와도 0을 처리 할 수 없다. 
• 이유는 오름차순으로 되어있는 숫자 배열은 숫자 크기를 비교할때 숫자들이 충분히 작기때문에 다음 숫자 처리전에 모두 처리된다.
• 하지만 내림차순의 경우, 왼쪽에 있는 숫자가 먼저 접근되고 처리가 실패된다면 뒤에 있는 작은 숫자는 처리가 될 수 없다. 
• 즉, 힙을 사용해서 배열의 가장 왼쪽의 숫자들을 계속 처리해줘야한다. 

소스 코드

class Solution:
    def secondGreaterElement(self, nums: List[int]) -> List[int]:
        st1, st2 = [], []
        ans = [-1 for i in range(len(nums))]
        heapify(st2)
        for i in range(len(nums)):
            while st2 and nums[-st2[0]] < nums[i]:
                ans[-heappop(st2)] = nums[i]
            while st1 and nums[st1[-1]] < nums[i]:
                heappush(st2, -st1.pop())
            st1.append(i)
        return ans