ቀጣይ ታላቁ ንጥረ ነገር እኔ Leetcode መፍትሔ  


የችግር ደረጃ ቀላል
ውስጥ በተደጋጋሚ ተጠየቀ አማዞን ብሉምበርግ
ስልተ ምስጠራ ቃለ መጠይቅ interviewprep ሊት ኮድ LeetCodeSolutions ክምር

የችግሩ መግለጫ  

በዚህ ችግር ውስጥ የመጀመሪያ ዝርዝር የሁለተኛ ዝርዝር ንዑስ ክፍል የሆኑ ሁለት ዝርዝሮች ተሰጥተናል ፡፡ ለእያንዳንዱ የመጀመሪያ ዝርዝር እያንዳንዱ አካል ፣ በሁለተኛው ዝርዝር ውስጥ የሚቀጥለውን ትልቁን ንጥረ ነገር መፈለግ አለብን ፡፡

ቀጣይ ታላቁ ንጥረ ነገር እኔ Leetcode መፍትሔጭንቅላታም መያያዣ መርፌ

ለምሳሌ

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

ማብራሪያ:

ለዝርዝር 1 የመጀመሪያ አካል ማለትም ለ 4 በዝርዝር 2 ውስጥ የሚቀጥለው ንጥረ ነገር የለም ፣ ስለሆነም መልሱ -1 ነው ፡፡
ለሁለተኛው ዝርዝር 1 ማለትም ለ 1 በዝርዝሩ 3 ውስጥ ከ 1 ይበልጣል ፣ ስለሆነም መልሱ 2 ነው ፡፡
ለሦስተኛው ዝርዝር 1 ማለትም ለ 2 በዝርዝር 2 ውስጥ የሚቀጥለው ንጥረ ነገር የለም ፣ ስለሆነም መልሱ -1 ነው።

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

አቀራረብ 1 (የጭካኔ ኃይል)  

በዚህ አካሄድ እኛ ለዝርዝር ጎጆ የሚሆን ጎብኝን በመጠቀም በዝርዝር 1 ውስጥ ቀጥተኛ መሻገሪያ በማድረግ ለእያንዳንዱ የሊስት 2 አካል ቀጣዩን የላቀ አካል እናገኛለን ፡፡
እያንዳንዱ የዝርዝር 1 ንጥረ ነገር በመጀመሪያ በዝርዝር 2 ውስጥ ይፈለጋል ፣ ከዚያ በኋላ የሚቀጥለው ትልቁ አካል ይፈለጋል። ባንዲራ ተለዋዋጭ በመጠቀም ይህንን እያደረግን ነው ፡፡ ለእያንዳንዱ የዝርዝር 1 አካል በመጀመሪያ ወደ ሐሰት ተቀናብሯል ፡፡ በዝርዝር 2 ውስጥ ያለውን ንጥረ ነገር ስናገኝ ወደ እውነት ተቀናብሯል ፡፡ ከዚያ በኋላ ፣ ቀጣዩን የላቀ ስናገኝ እንደገና ወደ ሐሰት እናቀጣለን ፡፡ ይህን በማድረጋችን ለዚያ ተለዋዋጭ በዝርዝር 2 ውስጥ ሌላ የሚቀጥለው ንጥረ ነገር እንዳለ እንገነዘባለን ወይም እንደሌለ እናውቃለን ፡፡

  • የባንዲራ ተለዋዋጭ እውነተኛ ከሆነ ለዚያ ንጥረ ነገር ከዚህ የበለጠ የላቀ እሴት ማግኘት አልቻልንም ማለት ነው።
  • የባንዲራ መለዋወጥ ውሸት ከሆነ ፣ ለዚያ አካል አንድ የሚቀጥለውን የበለጠ እሴት አግኝተናል ማለት ነው።
ተመልከት
ከፍተኛው የ 69 ቁጥር Leetcode መፍትሔ

ስለዚህ ፣ በእያንዳንዱ የውስጠኛው ዙር መጨረሻ ላይ እንደ ባንዲራ እሴታችን መሠረት -1 እንደ መልሳችን እንጨምራለን።

ለቀጣይ ታላቁ ንጥረ ነገር እኔ 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 መፍትሄ ውስብስብነት ትንተና

የጊዜ ውስብስብነት

ኦ (m * n): ለእያንዳንዱ የቁጥር ቁጥር 1 ቁጥርን ከግራ ወደ ቀኝ በመስመር ላይ እያለፍን ነው። ስለሆነም የጊዜ ውስብስብነት O (m * n) ሲሆን መ እና n የዝርዝሮች ርዝመት ናቸው ፡፡

የቦታ ውስብስብነት 

ኦ (1) ምንም ተጨማሪ ቦታ ጥቅም ላይ አልዋለም (ለአንስ ድርድር ጥቅም ላይ የዋለ ክፍተት አይታሰብም ምክንያቱም አስፈላጊ ነው)።

አቀራረብ 2 (ቁልል በመጠቀም)  

ይህ አካሄድ ሁለት ክፍሎችን ያቀፈ ነው ፡፡
በመጀመሪያ ፣ እኛ የሊስት 2 እያንዳንዱ ንጥረ ነገር ቀጣዩን ትልቁን ክፍል በመስመራዊ ጊዜ ለማግኘት ቁልል እየተጠቀምን ነው ፡፡ የእያንዳንዱ ንጥረ ነገር ቀጣይ ትልቁ ንጥረ ነገር በ ውስጥ ይቀመጣል ካርታ.
በሁለተኛ ደረጃ ካርታውን በመጠቀም የመልስ ዝርዝራችን ውስጥ ለእያንዳንዱ የዝርዝር 1 መልስ መልስ እናከማቻለን ፡፡

ስለዚህ ዝርዝሩን እናልፋለን እና ከአሁኑ ቁጥር ያነሱ እና በተመሳሳይ ጊዜ ከእያንዳንዱ ቁልል አናት ላይ ሁሉንም ንጥረ ነገሮችን ደጋግመን እናወጣቸዋለን ፣ በእያንዳንዱ ፖፕ ላይ የአሁኑን ንጥረ ነገር እንደ እያንዳንዱ ብቅ ያለ ንጥረ ነገር በጣም የቅርብ መልስ ሆኖ እንቀዳለን ፡፡ ለዚህ ካርታ በቀላሉ ካርታ እንጠቀማለን ፡፡
አሁን ፣ ከሚቀጥሉት ታላላቅ አባሎቻቸው ጋር የንጥሎች ካርታ ብቻ የሚሆን ካርታ አለን ፡፡
በመጨረሻም ፣ ዝርዝሩን 1 እናልፋለን እና በመልሶቻችን ዝርዝር ውስጥ የየራሳቸውን እሴቶች ከካርታ እናከማቸዋለን ፡፡

ተመልከት
የቃል ፍለጋ

ለቀጣይ ታላቁ ንጥረ ነገር እኔ 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 መፍትሄ ውስብስብነት ትንተና

የጊዜ ውስብስብነት

ኦ (m + n) በመጀመሪያ ፣ ለሊስት 2 አካላት በሙሉ የሚቀጥለውን የላቀ አካል ለማግኘት ዝርዝር 2 ን እየተጓዝን ነው ፡፡ ከዚያ እኛ መልሶችን ለመደመር ዝርዝር 1 እየተጓዝን ነው ፡፡ ስለዚህ ፣ የጊዜ ውስብስብነት የሁለቱም ዝርዝሮች ርዝመት ድምር ነው።

የቦታ ውስብስብነት 

ኦ (n): በ (1) ጊዜ ውስጥ ለማንኛውም ቁልፍ መልስ ለማግኘት ካርታ እየተጠቀምን ነው ፣ ስለሆነም የቦታ ውስብስብነት O (n) ነው።

1