Triplet Subsequence Artırılması LeetCode Həlli

Problem bəyanat :

Triplet Subsequence Artırılması LeetCode Həlli – Tam ədəd massivi verilmişdir nömrə, qayıt doğru üçlü indekslər varsa (i, j, k) belə i < j < k və ədədlər[i] < ədədlər[j] < ədədlər[k]. Əgər belə indekslər yoxdursa, qaytarın saxta.

Misal:

Misal 1:

Input: nums = [2,1,5,0,4,6]
Output: true
Explanation: The triplet (3, 4, 5) is valid because nums[3] == 0 < nums[4] == 4 < nums[5] == 6.

Misal 2:

Input: nums = [5,4,3,2,1]
Output: false
Explanation: No triplet exists.

Məhdudiyyətlər:

 

Müşahidə:

• Verilmiş məhdudiyyətlərdə massivin uzunluğu ola bilər 5*10^5, belə ki, kobud güc həlli O(n^2) və ya O(n^3) burada işləməyəcək, Brute force daha yaxşı bir şey etməliyik.
• Biz i < j < k istəyirik və nums[i] < nums[j] < nums[k], əgər biz ədədlər[i] yaratmağa çalışsaq mümkün qədər kiçik həm də düzəldir  ədəd[j] kiçikdir lakin nums[j] ədədlərdən[i] böyük olmalıdır ona görə də bizə kömək edəcək.
• Əgər müşahidə etsək, Xəsis alqoritm yaxşı işləyəcək.

Ən uzun artan alt ardıcıllığın variantı

• 2 x və y dəyişənini saxlamalıyıq.
• x indiyə qədər görülən ən kiçik ədəddir. x həm də indiyə qədər görülən bütün alt ardıcıllıqlar arasında ən kiçik sonuncu ədəddir.
• 2 ölçülü bütün artan alt ardıcıllıqları götürsək və alt ardıcıllığı s[0], s[1] kimi təqdim etsək; onda y min(s[1]).
• Hər hansı yeni z ədədi üçün z y-dən çox olarsa, bizim həllimiz var.

Alqoritm:

• İki dəyişən başlayın Zaman və orta ilə Tam ədəd.MAX_VALUE (Bütün MAKSİMUM DƏYƏR). 

int left=Tam.MAX_VALUE;

int orta = Tam ədəd.MAX_VALUE;

• Dan təkrarlayın soldan sağa ci nömrə serial.

• İterasiya zamanı aşağıdakı elementi tapmağa çalışın sağ > orta > sol şərt və bu elementi adlandırın sağ.

int sağ = ədədlər[i];

 

• Pin

 

 

• Əgər sağ kiçikdirr-dən solt dəyişəni sonra düzəldin sol = sağ.

Pin

 

                 

• Əgər hüququ var arasında bu solt və orta sonra ortadan doğru yerə keçin orta = sağ. Pin

• Əgər düzdür daha böyükdür solt və orta sonra qayıdın doğru.
• Döngə bitdikdən sonra Artan almadıqsa Triplet Sonrakı sonra qayıdın saxta.

Kod:

Üçlü Ardıcıllığı Artırmaq üçün Java Kodu:

class Solution {
    public boolean increasingTriplet(int[] nums) {
        int n= nums.length;
        int left=Integer.MAX_VALUE;
        int middle=Integer.MAX_VALUE;
        for(int i=0;i<n;i++){
            int right=nums[i];
            if(right<left){
                left=right;
            }
            else if(right<middle && right > left){
                middle = right;
            }
            else if(right>middle&& right>left)return true;
        }
        return false;
    }
    
}

Üçlü Ardıcıllığı Artırmaq üçün C++ Kodu:

class Solution {
public:
    bool increasingTriplet(vector<int>& nums) {
         int n= nums.size();
        int left=INT_MAX;
        int middle=INT_MAX;
        for(int i=0;i<n;i++){
            int right=nums[i];
            if(right<left){
                left=right;
            }
            else if(right<middle && right > left){
                middle = right;
            }
            else if(right>middle&& right>left)return true;
        }
        return false; 
    }
};

Üçlü Ardıcıllığın Artırılması üçün Mürəkkəblik Təhlili LeetCode Həlli:

Zamanın mürəkkəbliyi:

O (N)

Kosmik Mürəkkəblik:

O(1) çünki biz heç bir əlavə yerdən istifadə etmirik.