ਅਗਲਾ ਗ੍ਰੇਟਰ ਐਲੀਮੈਂਟ I ਲੀਟਕੋਡ ਹੱਲ


ਮੁਸ਼ਕਲ ਪੱਧਰ ਸੌਖੀ
ਅਕਸਰ ਪੁੱਛਿਆ ਜਾਂਦਾ ਹੈ ਐਮਾਜ਼ਾਨ ਬਲੂਮਬਰਗ
ਸਟੈਕ

ਸਮੱਸਿਆ ਦਾ ਬਿਆਨ

ਇਸ ਸਮੱਸਿਆ ਵਿੱਚ, ਸਾਨੂੰ ਦੋ ਸੂਚੀਆਂ ਦਿੱਤੀਆਂ ਗਈਆਂ ਹਨ ਜਿਸ ਵਿੱਚ ਪਹਿਲੀ ਸੂਚੀ ਦੂਜੀ ਸੂਚੀ ਦਾ ਉਪਸੈੱਟ ਹੈ. ਪਹਿਲੀ ਸੂਚੀ ਦੇ ਹਰੇਕ ਤੱਤ ਲਈ, ਸਾਨੂੰ ਦੂਜੀ ਸੂਚੀ ਵਿੱਚ ਅਗਲਾ ਵੱਡਾ ਤੱਤ ਲੱਭਣਾ ਪਏਗਾ.

ਅਗਲਾ ਗ੍ਰੇਟਰ ਐਲੀਮੈਂਟ I ਲੀਟਕੋਡ ਹੱਲ

ਉਦਾਹਰਨ

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

ਸਪਸ਼ਟੀਕਰਨ:

ਲਿਸਟ 1 ਦੇ ਪਹਿਲੇ ਐਲੀਮੈਂਟ ਲਈ, ਜਿਵੇਂ ਕਿ 4 ਲਈ ਲਿਸਟ 2 ਵਿੱਚ ਕੋਈ ਵੱਡਾ ਵੱਡਾ ਤੱਤ ਨਹੀਂ ਹੁੰਦਾ, ਇਸ ਤਰ੍ਹਾਂ ਇਸਦਾ ਉੱਤਰ -1 ਹੈ.
ਲਿਸਟ 1 ਦੇ ਦੂਸਰੇ ਐਲੀਮੈਂਟ ਲਈ, ਜਿਵੇਂ ਕਿ 1 ਲਈ ਲਿਸਟ 3 ਵਿਚ 1 ਤੋਂ 2 ਵੱਡਾ ਹੈ, ਇਸ ਤਰ੍ਹਾਂ ਇਸ ਦਾ ਜਵਾਬ 3 ਹੈ.
ਲਿਸਟ 1 ਦੇ ਤੀਜੇ ਐਲੀਮੈਂਟ ਦੇ ਲਈ ਭਾਵ 2 ਲਈ ਲਿਸਟ 2 ਵਿੱਚ ਅਗਲਾ ਵੱਡਾ ਕੋਈ ਤੱਤ ਨਹੀਂ ਹੈ, ਇਸ ਤਰ੍ਹਾਂ ਇਸਦਾ ਉੱਤਰ -1 ਹੈ

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

ਪਹੁੰਚ 1 (ਬਰੂਟ ਫੋਰਸ)

ਇਸ ਪਹੁੰਚ ਵਿੱਚ, ਅਸੀਂ ਲਿਸਟ ਲਈ ਇੱਕ ਨੇਸਟਡ ਲੂਪ ਦੀ ਵਰਤੋਂ ਕਰਕੇ ਲਿਸਟ 1 ਵਿੱਚ ਰੇਖਿਕ ਟ੍ਰਾਵਰਸਾਲ ਕਰਕੇ ਲਿਸਟ 2 ਦੇ ਹਰੇਕ ਤੱਤ ਲਈ ਅਗਲਾ ਵੱਡਾ ਤੱਤ ਲੱਭਦੇ ਹਾਂ.
ਸੂਚੀ 1 ਦੇ ਹਰੇਕ ਤੱਤ ਨੂੰ ਪਹਿਲਾਂ ਸੂਚੀ 2 ਵਿੱਚ ਖੋਜਿਆ ਜਾਂਦਾ ਹੈ, ਫਿਰ ਬਾਅਦ ਵਿੱਚ ਇਸਦੇ ਅਗਲੇ ਵੱਡੇ ਤੱਤ ਦੀ ਖੋਜ ਕੀਤੀ ਜਾਂਦੀ ਹੈ. ਅਸੀਂ ਫਲੈਗ ਵੇਰੀਏਬਲ ਦੀ ਵਰਤੋਂ ਕਰਕੇ ਇਹ ਕਰ ਰਹੇ ਹਾਂ. ਲਿਸਟ 1 ਦੇ ਹਰੇਕ ਤੱਤ ਲਈ, ਇਹ ਪਹਿਲਾਂ ਗਲਤ ਤੇ ਸੈਟ ਕੀਤਾ ਗਿਆ ਹੈ. ਜਦੋਂ ਸਾਨੂੰ ਲਿਸਟ 2 ਵਿੱਚ ਐਲੀਮੈਂਟ ਮਿਲਿਆ ਹੈ, ਇਹ ਸਹੀ ਤੇ ਸੈਟ ਕੀਤਾ ਜਾਂਦਾ ਹੈ. ਉਸ ਤੋਂ ਬਾਅਦ, ਜਦੋਂ ਸਾਨੂੰ ਅਗਲਾ ਵੱਡਾ ਪਤਾ ਲੱਗੇਗਾ, ਅਸੀਂ ਇਸਨੂੰ ਫਿਰ ਗਲਤ ਤੇ ਸੈਟ ਕਰ ਦੇਵਾਂਗੇ. ਅਜਿਹਾ ਕਰਨ ਨਾਲ, ਸਾਨੂੰ ਪਤਾ ਲੱਗ ਜਾਵੇਗਾ ਕਿ ਉਸ ਵੇਰੀਏਬਲ ਲਈ ਲਿਸਟ 2 ਵਿਚ ਕੋਈ ਅਗਲਾ ਵੱਡਾ ਤੱਤ ਹੈ ਜਾਂ ਕੋਈ ਵੀ ਨਹੀਂ ਹੈ.

  • ਜੇ ਫਲੈਗ ਵੇਰੀਏਬਲ ਸਹੀ ਹੈ, ਤਾਂ ਇਸਦਾ ਮਤਲਬ ਹੈ ਕਿ ਅਸੀਂ ਉਸ ਐਲੀਮੈਂਟ ਲਈ ਕੋਈ ਵੱਡਾ ਵੱਡਾ ਮੁੱਲ ਨਹੀਂ ਲੱਭ ਸਕੇ.
  • ਜੇ ਫਲੈਗ ਵੇਰੀਏਬਲ ਗਲਤ ਹੈ, ਤਾਂ ਇਸਦਾ ਅਰਥ ਹੈ ਕਿ ਸਾਨੂੰ ਉਸ ਤੱਤ ਲਈ ਅਗਲਾ ਵੱਡਾ ਮੁੱਲ ਮਿਲਿਆ ਹੈ.

ਤਾਂ, ਹਰੇਕ ਅੰਦਰੂਨੀ ਲੂਪ ਦੇ ਅੰਤ ਤੇ, ਫਲੈਗ ਵੈਲਯੂ ਦੇ ਅਨੁਸਾਰ ਅਸੀਂ ਆਪਣੇ ਜਵਾਬ ਦੇ ਰੂਪ ਵਿੱਚ -1 ਪਾਵਾਂਗੇ.

ਨੈਕਸਟ ਗਰੇਟਰ ਐਲੀਮੈਂਟ I ਲੀਟਕੋਡ ਸਲਿ .ਸ਼ਨ ਲਈ ਲਾਗੂਕਰਣ

ਸੀ ++ ਪ੍ਰੋਗਰਾਮ

#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 ਲੀਟਕੋਡ ਹੱਲ ਲਈ ਜਟਿਲਤਾ ਵਿਸ਼ਲੇਸ਼ਣ

ਟਾਈਮ ਜਟਿਲਤਾ

ਓ (ਐਮ * ਐਨ): ਨੰਬਰ 1 ਦੇ ਹਰ ਇੱਕ ਤੱਤ ਲਈ ਅਸੀਂ ਖੱਬੇ ਤੋਂ ਸੱਜੇ ਨੰਬਰ 2 ਨੂੰ ਲੰਘ ਰਹੇ ਹਾਂ. ਇਸ ਪ੍ਰਕਾਰ, ਸਮਾਂ ਗੁੰਝਲਤਾ O (m * n) ਹੈ ਜਿਥੇ m ਅਤੇ n ਸੂਚੀਆਂ ਦੀ ਲੰਬਾਈ ਹਨ.

ਸਪੇਸ ਦੀ ਜਟਿਲਤਾ 

ਓ (1): ਕੋਈ ਵਾਧੂ ਥਾਂ ਨਹੀਂ ਵਰਤੀ ਗਈ (ਅੰਸ ਐਰੇ ਲਈ ਵਰਤੀ ਗਈ ਥਾਂ ਨਹੀਂ ਮੰਨੀ ਜਾਂਦੀ ਕਿਉਂਕਿ ਇਹ ਜ਼ਰੂਰੀ ਹੈ).

ਪਹੁੰਚ 2 (ਸਟੈਕ ਦੀ ਵਰਤੋਂ ਕਰਦਿਆਂ)

ਇਸ ਪਹੁੰਚ ਵਿਚ ਦੋ ਹਿੱਸੇ ਸ਼ਾਮਲ ਹਨ.
ਪਹਿਲਾਂ, ਅਸੀਂ ਲਕੀਰ ਸਮੇਂ ਵਿੱਚ ਲਿਸਟ 2 ਦੇ ਹਰੇਕ ਤੱਤ ਦੇ ਅਗਲੇ ਵੱਡੇ ਤੱਤ ਨੂੰ ਪ੍ਰਾਪਤ ਕਰਨ ਲਈ ਇੱਕ ਸਟੈਕ ਦੀ ਵਰਤੋਂ ਕਰ ਰਹੇ ਹਾਂ. ਹਰੇਕ ਤੱਤ ਦਾ ਅਗਲਾ ਵੱਡਾ ਤੱਤ a ਵਿੱਚ ਸਟੋਰ ਕੀਤਾ ਜਾਂਦਾ ਹੈ ਫੋਲਡਰ ਨੂੰ.
ਦੂਜਾ, ਅਸੀਂ ਨਕਸ਼ੇ ਦੀ ਵਰਤੋਂ ਕਰਕੇ ਲਿਸਟ 1 ਦੇ ਹਰੇਕ ਐਲੀਮੈਂਟ ਲਈ ਆਪਣੀ ਜਵਾਬ ਐਰੇ ਵਿੱਚ ਸਟੋਰ ਕਰਾਂਗੇ.

ਇਸ ਲਈ, ਅਸੀਂ ਲਿਸਟ 2 ਨੂੰ ਪਾਰ ਕਰਾਂਗੇ ਅਤੇ ਬਾਰ ਬਾਰ ਸਾਰੇ ਤੱਤਾਂ ਨੂੰ ਸਟੈਕ ਦੇ ਸਿਖਰ ਤੋਂ ਪੌਪ ਕਰਾਂਗੇ ਜੋ ਮੌਜੂਦਾ ਨੰਬਰ ਨਾਲੋਂ ਛੋਟੇ ਹਨ ਅਤੇ ਇਕੋ ਸਮੇਂ, ਹਰ ਪੌਪ 'ਤੇ ਅਸੀਂ ਮੌਜੂਦਾ ਪੌਸ਼ਟਿਕ ਤੱਤ ਨੂੰ ਹਰੇਕ ਪੌਪ ਕੀਤੇ ਤੱਤ ਦੇ ਸਭ ਤੋਂ ਨੇੜਲੇ ਉੱਤਰ ਵਜੋਂ ਰਿਕਾਰਡ ਕਰਾਂਗੇ. ਇਸ ਮੈਪਿੰਗ ਲਈ, ਅਸੀਂ ਸਿਰਫ਼ ਇੱਕ ਨਕਸ਼ੇ ਦੀ ਵਰਤੋਂ ਕਰਾਂਗੇ.
ਹੁਣ, ਸਾਡੇ ਕੋਲ ਇੱਕ ਨਕਸ਼ਾ ਹੈ ਜੋ ਉਹਨਾਂ ਦੇ ਅਗਲੇ ਵੱਡੇ ਤੱਤ ਦੇ ਨਾਲ ਤੱਤਾਂ ਦਾ ਸਿਰਫ ਇੱਕ ਮੈਪਿੰਗ ਹੈ.
ਅੰਤ ਵਿੱਚ, ਅਸੀਂ ਸੂਚੀ 1 ਨੂੰ ਪਾਰ ਕਰਾਂਗੇ ਅਤੇ ਉਹਨਾਂ ਦੇ ਸਬੰਧਤ ਮੁੱਲਾਂ ਨੂੰ ਸਾਡੀ ਉੱਤਰ ਸੂਚੀ ਵਿੱਚ ਨਕਸ਼ੇ ਤੋਂ ਸਟੋਰ ਕਰਾਂਗੇ.

ਨੈਕਸਟ ਗਰੇਟਰ ਐਲੀਮੈਂਟ I ਲੀਟਕੋਡ ਸਲਿ .ਸ਼ਨ ਲਈ ਲਾਗੂਕਰਣ

ਸੀ ++ ਪ੍ਰੋਗਰਾਮ

#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 ਲੀਟਕੋਡ ਹੱਲ ਲਈ ਜਟਿਲਤਾ ਵਿਸ਼ਲੇਸ਼ਣ

ਟਾਈਮ ਜਟਿਲਤਾ

ਓ (ਐਮ + ਐਨ): ਪਹਿਲਾਂ, ਅਸੀਂ ਲਿਸਟ 2 ਦੇ ਸਾਰੇ ਤੱਤਾਂ ਲਈ ਅਗਲਾ ਵੱਡਾ ਤੱਤ ਲੱਭਣ ਲਈ ਲਿਸਟ 2 ਨੂੰ ਟ੍ਰਾਵਰ ਕਰ ਰਹੇ ਹਾਂ. ਫਿਰ, ਅਸੀਂ ਜਵਾਬ ਜੋੜਨ ਲਈ ਲਿਸਟ 1 ਨੂੰ ਟ੍ਰਾਵਰ ਕਰ ਰਹੇ ਹਾਂ. ਤਾਂ, ਸਮਾਂ ਗੁੰਝਲਤਾ ਦੋਵਾਂ ਸੂਚੀਆਂ ਦੀ ਲੰਬਾਈ ਦਾ ਜੋੜ ਹੈ.

ਸਪੇਸ ਦੀ ਜਟਿਲਤਾ 

ਓ (ਐਨ): ਅਸੀਂ ਓ (1) ਸਮੇਂ ਵਿੱਚ ਕਿਸੇ ਵੀ ਕੁੰਜੀ ਦਾ ਉੱਤਰ ਲੱਭਣ ਲਈ ਇੱਕ ਨਕਸ਼ੇ ਦੀ ਵਰਤੋਂ ਕਰ ਰਹੇ ਹਾਂ, ਇਸ ਤਰ੍ਹਾਂ ਸਪੇਸ ਦੀ ਜਟਿਲਤਾ ਓ (ਐਨ) ਹੈ.