다음 더 큰 요소 I Leetcode 솔루션


난이도 쉽게
자주 묻는 질문 아마존 블룸버그
스택

문제 정책

이 문제에서는 첫 번째 목록이 두 번째 목록의 하위 집합 인 두 개의 목록이 제공됩니다. 첫 번째 목록의 각 요소에 대해 두 번째 목록에서 다음으로 큰 요소를 찾아야합니다.

다음 더 큰 요소 I Leetcode 솔루션

nums1 = [4,1,2], nums2 = [1,3,4,2]
[-1,3,-1]

설명 :

list1의 첫 번째 요소, 즉 4의 경우 list2에는 다음으로 큰 요소가 없으므로 그 답은 -1입니다.
list1의 두 번째 요소, 즉 1의 경우 목록 3에서 1보다 큰 2이 있으므로 그 답은 3입니다.
list1의 세 번째 요소, 즉 2의 경우 list2에 다음으로 큰 요소가 없으므로 그 답은 -1입니다.

nums1 = [2,4], nums2 = [1,2,3,4]
[3,-1]

접근 1 (Brute Force)

이 접근 방식에서는 중첩 된 for 루프를 사용하여 list1에서 선형 순회를 수행하여 list2의 각 요소에 대해 다음으로 큰 요소를 간단히 찾습니다.
list1의 각 요소는 먼저 list2에서 검색된 다음 그 다음으로 큰 요소가 검색됩니다. 플래그 변수를 사용하여이를 수행합니다. list1의 각 요소에 대해 먼저 false로 설정됩니다. list2에서 요소를 찾으면 true로 설정됩니다. 그 후 다음 더 큰 것을 찾을 때 다시 false로 설정합니다. 이렇게하면 해당 변수에 대해 list2에 다음으로 큰 요소가 있는지 또는 없는지 알 수 있습니다.

  • 플래그 변수가 참이면 해당 요소에 대해 다음으로 큰 값을 찾을 수 없음을 의미합니다.
  • 플래그 변수가 거짓이면 해당 요소에 대해 다음으로 큰 값을 찾았다는 의미입니다.

따라서 각 내부 루프의 끝에 플래그 값에 따라 답변으로 -1을 삽입합니다.

차세대 요소 I Leetcode 솔루션 구현

C ++ 프로그램

#include <iostream>
#include <vector>
using namespace std;
vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
        vector<int> ans;
        for(int i=0;i<nums1.size();i++){
            bool flag=false;
            for(int j=0;j<nums2.size();j++){
                if(nums1[i]==nums2[j])flag=true;
                if(flag && nums1[i]<nums2[j]){
                    ans.push_back(nums2[j]);flag=false;break;
                }
            }
            if(flag)ans.push_back(-1);
            
        }
        return ans;
    }
int main()
{
    vector<int> nums1{ 4,1,2 }; 
    vector<int> nums2{ 1,3,4,2 }; 
    vector<int>ans=nextGreaterElement(nums1,nums2);
    for(int i=0;i<ans.size();i++){
        cout<<ans[i]<<" ";
    }
}
-1 3 -1

자바 프로그램

import java.util.*;
import java.lang.*;

class Solution
{  
    public static void main(String args[])
    {
        int[]nums1={4,1,2};
        int[]nums2={1,3,4,2};
        int[]ans=nextGreaterElement(nums1,nums2);
        for(int i:ans){
            System.out.print(i+" ");
        }
            
        
    }
    public static int[] nextGreaterElement(int[] nums1, int[] nums2) {
        int[]ans=new int[nums1.length];
        for(int i=0;i<nums1.length;i++){
            boolean flag=false;
            for(int j=0;j<nums2.length;j++){
                if(nums1[i]==nums2[j])flag=true;
                if(flag && nums1[i]<nums2[j]){
                    ans[i]=nums2[j];flag=false;break;
                }
            }
            if(flag)ans[i]=-1;
            
        }
        return ans;
    }
}
-1 3 -1

차세대 요소 I Leetcode 솔루션에 대한 복잡성 분석

시간 복잡성

O (m * n) : nums1의 각 요소에 대해 nums2를 왼쪽에서 오른쪽으로 선형으로 이동합니다. 따라서 시간 복잡도는 O (m * n)이며 여기서 m과 n은 목록의 길이입니다.

공간 복잡성 

O (1) : 추가 공간이 사용되지 않습니다 (ANS 배열에 사용 된 공간은 필요하기 때문에 고려되지 않습니다).

접근 방식 2 (스택 사용)

이 접근 방식은 두 부분으로 구성됩니다.
첫째, 스택을 사용하여 선형 시간에서 list2의 각 요소에서 다음으로 큰 요소를 가져옵니다. 각 요소의 다음으로 큰 요소는 지도.
둘째, map을 사용하여 list1의 각 요소에 대한 답변을 답변 배열에 저장합니다.

따라서 list2를 탐색하고 현재 숫자보다 작은 스택 상단의 모든 요소를 ​​반복적으로 팝하고 동시에 각 팝에서 현재 요소를 팝된 각 요소의 가장 가까운 큰 답변으로 기록합니다. 이 매핑에서는 단순히지도를 사용합니다.
이제 우리는 그 다음으로 큰 요소를 가진 요소의 매핑 일 뿐인 맵을 가지고 있습니다.
마지막으로 list1을 탐색하고 맵의 각 값을 답변 목록에 저장합니다.

차세대 요소 I Leetcode 솔루션 구현

C ++ 프로그램

#include <iostream>
#include <vector>
#include <stack>
#include <map>
using namespace std;
vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
        stack<int>stack;
        map<int,int>map;
        vector<int>ans;
        for(int i=0;i<nums2.size();i++){
            while(!stack.empty()){
                if(stack.top()<nums2[i]){
                    map.insert(pair<int,int>(stack.top(),nums2[i]));
                    stack.pop();
                }else break;
            }
            stack.push(nums2[i]);
        }
        
        for(int i=0;i<nums1.size();i++){
            int val = map[nums1[i]];
            if(val==0)ans.push_back(-1);
            else ans.push_back(val);
        }
        return ans;
    }
int main()
{
    vector<int> nums1{ 4,1,2 }; 
    vector<int> nums2{ 1,3,4,2 }; 
    vector<int>ans=nextGreaterElement(nums1,nums2);
    for(int i=0;i<ans.size();i++){
        cout<<ans[i]<<" ";
    }
}
-1 3 -1

자바 프로그램

import java.util.*;
import java.lang.*;

class Solution
{  
    public static void main(String args[])
    {
        int[]nums1={4,1,2};
        int[]nums2={1,3,4,2};
        int[]ans=nextGreaterElement(nums1,nums2);
        for(int i:ans){
            System.out.print(i+" ");
        }
            
        
    }
    public static int[] nextGreaterElement(int[] nums1, int[] nums2) {
        Stack<Integer>stack=new Stack<Integer>();
        Map<Integer,Integer>map=new HashMap<Integer,Integer>();
        int[]ans=new int[nums1.length];
        for(int i:nums2){
            while(!stack.isEmpty()){
                if(stack.peek()<i){
                    map.put(stack.peek(),i);
                    stack.pop();
                }else break;
            }
            stack.push(i);
        }
        for(int i=0;i<nums1.length;i++){
            if(map.containsKey(nums1[i]))
            ans[i]=map.get(nums1[i]);
            else ans[i]=-1;
        }
        return ans;
    }
}
-1 3 -1

차세대 요소 I Leetcode 솔루션에 대한 복잡성 분석

시간 복잡성

O (m + n) : 첫째, list2의 모든 요소에 대해 다음으로 큰 요소를 찾기 위해 list2를 순회합니다. 그런 다음 list1을 탐색하여 답변을 추가합니다. 따라서 시간 복잡도는 두 목록 길이의 합계입니다.

공간 복잡성 

의 위에): 우리는지도를 사용하여 O (1) 시간의 모든 키에 대한 답을 찾고 있으므로 공간 복잡성은 O (n)입니다.