Next Greater Element I(Array,Hash Table,Stack,Monotonic Stack)

https://leetcode.com/problems/next-greater-element-i/description/

The next greater element of some element x in an array is the first greater element that is to the right of x in the same array.

You are given two distinct 0-indexed integer arrays nums1 and nums2, where nums1 is a subset of nums2.

For each 0 <= i < nums1.length, find the index j such that nums1[i] == nums2[j] and determine the next greater element of nums2[j] in nums2. If there is no next greater element, then the answer for this query is -1.

Return an array ans of length nums1.length such that ans[i] is the next greater element as described above.

 

Example 1:

Input: nums1 = [4,1,2], nums2 = [1,3,4,2]
Output: [-1,3,-1]
Explanation: The next greater element for each value of nums1 is as follows:
- 4 is underlined in nums2 = [1,3,4,2]. There is no next greater element, so the answer is -1.
- 1 is underlined in nums2 = [1,3,4,2]. The next greater element is 3.
- 2 is underlined in nums2 = [1,3,4,2]. There is no next greater element, so the answer is -1.

Example 2:

Input: nums1 = [2,4], nums2 = [1,2,3,4]
Output: [3,-1]
Explanation: The next greater element for each value of nums1 is as follows:
- 2 is underlined in nums2 = [1,2,3,4]. The next greater element is 3.
- 4 is underlined in nums2 = [1,2,3,4]. There is no next greater element, so the answer is -1.

 

Constraints:

• 1 <= nums1.length <= nums2.length <= 1000
• 0 <= nums1[i], nums2[i] <= 104
• All integers in nums1 and nums2 are unique.
• All the integers of nums1 also appear in nums2.

 

Follow up: Could you find an O(nums1.length + nums2.length) solution?

 

일단 난이도는 Easy로 책정되어있다. 그만큼 만만할 수도 있다는 것이다. 한 번 좀 쳐보자~

 

 

1. Python

from typing import List
class Solution:
    def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]:
        ans = []
        n = len(nums2)
        for x in nums1:
            idx = nums2.index(x)
            cond = False
            for y in range(idx+1,n):
                if nums2[y] > x :
                    ans.append(nums2[y])
                    cond = True
                    break
            if not cond : ans.append(-1)
        
        return ans

 

뭐.. 그닥 어려운 느낌은 안 들어서 Naive하게 풀어보았다. Key point는 Python Array에서 index 라는 method를 써서 푼 것

뭔가 성적은 좋지 않아서, 더 빨리 푼 Code가 있는지 참고해보기로 한다.

 

내 Coding의 원칙. 일단 내 code가 답을 도출해냈으면, 나는 다른 이들의 답안을 볼 권리를 얻은 것..!

 

근데,, stack 과 hash table을 썼다는데 솔직히 code를 봐도 잘 모르겠다..

class Solution:
    def nextGreaterElement(self, nums1, nums2):
        stack = []
        hashmap = {}

        for num in nums2:
            while stack and num > stack[-1]:
                hashmap[stack.pop()] = num
            stack.append(num)

        # while stack:
        #     hashmap[stack.pop()] = -1

        return [hashmap.get(i, -1) for i in nums1] #-1 is default value if the key i isn't present in the hashmap

class Solution:
    def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]:
        ng = {}
        s = []
        for i in reversed(nums2):
            while s and s[-1] <= i:
                s.pop()
            ng[i] = s[-1] if s else -1
            s.append(i)

        return [ng[i] for i in nums1]

 

 

2. C++

C++ stack을 한 번 써 볼까나..?

찬찬~히 보다보면 코드가 이해가 가긴 한다.

 

재밌다 ㅋㅋ

class Solution {
public:
    vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
        stack<int> s;
        map<int,int> m;
        
        for(int i=nums2.size()-1;i>=0;i--){
            int temp = nums2[i];
            while(!s.empty() && temp > s.top()){
                s.pop();
            }
            if(s.empty()) m[temp] = -1;
            else m[temp] = s.top();
            s.push(temp);
        }
        for(int j=0;j<nums1.size();j++){
            nums1[j] = m[nums1[j]];
        }
        return nums1;
    }
};

 

첨엔 뭔 소린가 했는데, 막상 이해하고나면 이렇게 깔끔할 순 없다.

 

Brute Force가 허용되지 않는다고하면 꽤나 수학적이었던 문제!