அடுத்த கிரேட்டர் உறுப்பு I லீட்கோட் தீர்வு  


சிரமம் நிலை எளிதாக
அடிக்கடி கேட்கப்படுகிறது அமேசான் ப்ளூம்பெர்க்
குறியீட்டு பேட்டி நேர்காணல் தயாரிப்பு லீட்கோட் LeetCodeSolutions ஸ்டேக்

சிக்கல் அறிக்கை  

இந்த சிக்கலில், எங்களுக்கு இரண்டு பட்டியல்கள் வழங்கப்பட்டுள்ளன, அதில் முதல் பட்டியல் இரண்டாவது பட்டியலின் துணைக்குழு ஆகும். முதல் பட்டியலின் ஒவ்வொரு உறுப்புக்கும், இரண்டாவது பட்டியலில் அடுத்த பெரிய உறுப்பைக் கண்டுபிடிக்க வேண்டும்.

அடுத்த கிரேட்டர் உறுப்பு 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 இன் ஒவ்வொரு உறுப்புக்கும் அடுத்த பெரிய உறுப்பைக் கண்டுபிடிப்போம்.
பட்டியல் 1 இன் ஒவ்வொரு உறுப்புகளும் முதலில் பட்டியல் 2 இல் தேடப்படுகின்றன, பின்னர் அதன் அடுத்த பெரிய உறுப்பு தேடப்படுகிறது. கொடி மாறியைப் பயன்படுத்தி இதைச் செய்கிறோம். பட்டியல் 1 இன் ஒவ்வொரு உறுப்புக்கும், இது முதலில் தவறானதாக அமைக்கப்படுகிறது. பட்டியல் 2 இல் உள்ள உறுப்பைக் கண்டறிந்ததும், அது உண்மை என அமைக்கப்படுகிறது. அதன்பிறகு, அடுத்த பெரியதைக் காணும்போது, ​​அதை மீண்டும் பொய்யாக அமைப்போம். அவ்வாறு செய்வதன் மூலம், அந்த மாறிக்கான பட்டியல் 2 இல் அடுத்த பெரிய உறுப்பு ஏதேனும் உள்ளதா அல்லது எதுவும் இல்லை என்பதை அறிந்து கொள்வோம்.

  • கொடி மாறி உண்மையாக இருந்தால், அந்த உறுப்புக்கான அடுத்த பெரிய மதிப்பை எங்களால் கண்டுபிடிக்க முடியவில்லை.
  • கொடி மாறி தவறானது என்றால், அந்த உறுப்புக்கு அடுத்த ஒரு பெரிய மதிப்பைக் கண்டுபிடித்தோம் என்று அர்த்தம்.
மேலும் காண்க
அதிகபட்சம் 69 எண் லீட்கோட் தீர்வு

எனவே, ஒவ்வொரு உள் வளையத்தின் முடிவிலும், கொடி மதிப்பின் படி -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 லீட்கோட் தீர்வுக்கான சிக்கலான பகுப்பாய்வு

நேர சிக்கலானது

O (m * n): எண் 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 லீட்கோட் தீர்வுக்கான சிக்கலான பகுப்பாய்வு

நேர சிக்கலானது

O (m + n): முதலாவதாக, பட்டியல் 2 இன் அனைத்து உறுப்புகளுக்கும் அடுத்த பெரிய உறுப்பைக் கண்டுபிடிக்க பட்டியல் 2 ஐக் கடந்து செல்கிறோம். பின்னர், பதில்களைச் சேர்க்க பட்டியல் 1 ஐக் கடந்து செல்கிறோம். எனவே, நேர சிக்கலானது இரு பட்டியல்களின் நீளத்தின் கூட்டுத்தொகையாகும்.

விண்வெளி சிக்கலானது 

ஓ (ந): O (1) நேரத்தில் எந்த விசைக்கும் பதில் கண்டுபிடிக்க ஒரு வரைபடத்தைப் பயன்படுத்துகிறோம், இதனால் இட சிக்கலானது O (n) ஆகும்.

1