ווייַטער גרייטער עלעמענט איך לעעטקאָדע סאַלושאַן


שוועריקייט לעוועל גרינג
אָפט געבעטן אין אַמאַזאָן בלומבערג
אָנלייגן

פּראָבלעם סטאַטעמענט

אין דעם פּראָבלעם, מיר באַקומען צוויי רשימות אין וועלכע דער ערשטער רשימה איז סאַבסעט פון די רגע רשימה. פֿאַר יעדער עלעמענט פון דער ערשטער רשימה, מיר מוזן געפֿינען די ווייַטער גרעסערע עלעמענט אין דער רגע רשימה.

ווייַטער גרייטער עלעמענט איך לעעטקאָדע סאַלושאַן

בייַשפּיל

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 ווי אונדזער ענטפער.

ימפּלעמענטאַטיאָן פֿאַר דער ווייַטער גרעסער עלעמענט איך לעעטקאָדע סאַלושאַן

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

Java פּראָגראַם

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

קאַמפּלעקסיטי אַנאַליסיס פֿאַר ווייַטער גרעסער עלעמענט איך לעעטקאָדע סאַלושאַן

צייט קאַמפּלעקסיטי

אָ (m * n): פֿאַר יעדער עלעמענט פון נומס 1, מיר זענען דורכגעקאָכט נומס 2 לינעאַרלי פֿון לינקס צו רעכטס. צייט קאַמפּלעקסיטי איז אַזוי אָ (m * n) ווו m און n זענען לענג פון רשימות.

ספעיס קאַמפּלעקסיטי 

אָ (1): קיין עקסטרע פּלאַץ געוויינט (ספּייסט געוויינט פֿאַר אַנס מענגע איז נישט באַטראַכט ווייַל דאָס איז נייטיק).

צוגאַנג 2 (ניצן סטאַק)

דער צוגאַנג קאַמפּרייזיז פון צוויי טיילן.
פירסטלי, מיר נוצן אַ אָנלייגן צו באַקומען די ווייַטער גרעסערע עלעמענט פון יעדער עלעמענט פון ליסט 2 אין לינעאַר צייט. דער ווייַטער גרעסערער עלעמענט פון יעדער עלעמענט איז סטאָרד אין אַ מאַפּע.
צווייטנס, מיר וועלן האַלטן די ענטפֿערס פֿאַר יעדער עלעמענט פון ליסט 1 אין אונדזער ענטפער מיט די מאַפּע.

דעריבער, מיר וועלן דורכגיין די ליסט 2 און ריפּיטידלי פּאָפּ אַלע עלעמענטן פֿון די שפּיץ פון די אָנלייגן וואָס זענען קלענערער ווי די קראַנט נומער און סיימאַלטייניאַסלי.אין יעדער קנאַל, מיר וועלן רעקאָרדירן דעם קראַנט עלעמענט ווי די ניראַסט גרעסערע ענטפער פון יעדער פּאַפּט עלעמענט. פֿאַר דעם מאַפּינג, מיר וועלן פשוט נוצן אַ מאַפּע.
איצט מיר האָבן אַ מאַפּע וואָס איז בלויז אַ מאַפּינג פון עלעמענטן מיט זייער ריספּעקטיוו ווייַטער גרעסערע עלעמענטן.
לעסאָף מיר וועלן אַריבער די ליסט 1 און קראָם זייער ריספּעקטיוו וואַלועס פֿון מאַפּע אין אונדזער ענטפֿערן רשימה.

ימפּלעמענטאַטיאָן פֿאַר דער ווייַטער גרעסער עלעמענט איך לעעטקאָדע סאַלושאַן

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

Java פּראָגראַם

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

קאַמפּלעקסיטי אַנאַליסיס פֿאַר ווייַטער גרעסער עלעמענט איך לעעטקאָדע סאַלושאַן

צייט קאַמפּלעקסיטי

אָ (m + n): פירסטלי, מיר גיין דורך ליסט 2 צו געפֿינען די ווייַטער גרעסערע עלעמענט פֿאַר אַלע יסודות פון ליסט 2. דערנאָך, מיר גיין דורך רשימה 1 צו צולייגן די ענטפֿערס. צייט קאַמפּלעקסיטי איז די גאַנץ לענג פון ביידע רשימות.

ספעיס קאַמפּלעקסיטי 

אָ (n): מיר נוצן אַ מאַפּע צו געפֿינען ענטפֿערס צו קיין שליסל אין די O (1) צייט, אַזוי די פּלאַץ קאַמפּלעקסיטי איז O (n).