문제를 이해하고 있다면 바로 풀이를 보면 됨
전체 코드로 바로 넘어가도 됨
마음대로 번역해서 오역이 있을 수 있음

Problem

배열에서 어떤 요소 x의 다음으로 큰 요소는 x의 오른쪽에 있는 첫 번째 큰 요소이다.

서로 다른 두 개의 0부터 시작하는 인덱스를 가진 정수 배열 nums1과 nums2가 주어진다. nums1은 nums2의 부분집이다.

0 <= i < nums1.length인 각 인덱스 j에 대해 nums1[i] == nums2[j]를 만족하는 인덱스 j를 찾고, nums2[j]에서 nums2[j]보다 다음으로 큰 요소를 찾아라. 다음으로 큰 요소가 없으면 -1을 반환해라.

위에서 설명한 대로 ans[i]가 다음으로 큰 요소가 되는 nums1.length 길이의 배열 ans를 반환해라.

Example

#1
Input: nums1 = [4, 1, 2], nums2 = [1, 3, 4, 2]
Output: [-1, 3, -1]
Explanation: nums1의 각 값에 대한 다음으로 큰 원소는 다음과 같다.

• nums2 = [1, 3, 4, 2]에 4 다음으로 큰 원소가 없으므로 답은 -1이다.
• nums2 = [1, 3, 4, 2]에 1 다음으로 큰 원소는 3이다.
• nums2 = [1, 3, 4, 2]에 2 다음으로 큰 원소가 없으므로 답은 -1이다.

#2
Input: nums1 = [2, 4], nums2 = [1, 2, 3, 4]
Output: [3, 1]
Explanation: nums1의 각 값에 대한 다음으로 큰 원소는 다음과 같다.

• nums2 = [1, 2, 3, 4]에서 2 다음으로 큰 원소는 3이다.
• nums2 = [1, 2, 3, 4]에서 4 다음으로 큰 원소가 없으므로 답은 -1이다.

Constraints

• 1 <= nums1.length <= nums2.length <= 1000
• 0 <= nums1[i], nums2[i] <= 10^4
• nums1과 num2에 있는 모든 정수는 고유하다.
• nums1에 있는 모든 정수는 nums2에 나타날 수 있다.

Solved

class Solution {
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        Map<Integer, Integer> ng = new HashMap<>();
        Deque<Integer> st = new ArrayDeque<>();

        for(int num : nums2){
            while(!st.isEmpty() && st.peek() < num){
                ng.put(st.pop(), num);
            }

            st.push(num);
        }

        int[] result = new int[nums1.length];

        for(int i = 0; i < nums1.length; i++){
            result[i] = ng.getOrDefault(nums1[i], -1);
        }

        return result;
    }
}