ඉහළම ස්ථානයට පෙර දෙවන ඉහළම බොරු ඇති උප කුලක ගණන් කරන්න


දුෂ්කරතා මට්ටම මධ්යම
නිතර අසනු ලැබේ හැකර් රැන්ක්
අරා අඩුක්කුව

ගැටළු ප්රකාශය

“ඉහළම ස්ථානයට පෙර දෙවන ඉහළම බොරුව ඇති උප කුලක ගණන් කරන්න” යන ගැටලුවේ සඳහන් වන්නේ ඔබට ලබා දී ඇති බවයි අරාව n [2] ට වඩා විශාල හෝ සමාන වන n [XNUMX] ට වඩා වැඩි හෝ සමාන වේ.

ඉහළම ස්ථානයට පෙර දෙවන ඉහළම බොරු ඇති උප කුලක ගණන් කරන්න

උදාහරණයක්

 a[ ] = {1, 3, 2, 4}
3
a[ ] = {1, 2, 3}
2

ඇල්ගොරිතම

  1. N ප්‍රමාණයේ [] අරාවක් ආරම්භ කරන්න.
  2. තුනක් සාදන්න අරා පෙර විශාල මූලද්‍රව්‍යය, ඊළඟ විශාල මූලද්‍රව්‍යය සහ උපරිම මූලද්‍රව්‍යය පිළිවෙලින් ගබඩා කිරීමට. පිළිතුර ගබඩා කිරීම සඳහා විචල්‍යයක් ප්‍රකාශ කර එහි අගය 0 ලෙස සකසන්න.
  3. සාදන්න අඩුයි වර්ගයේ පූර්ණ සංඛ්‍යා යුගල.
  4. 0 සිට n-1 දක්වා ගමන් කර පෙර විශාල මූලද්‍රව්‍ය අරාවේ වත්මන් දර්ශකයේ අගය -1 ලෙස සකසන්න. අට්ටාලය හිස් නොවන අතර, තොගයේ ඉහළින් ඇති යුගලයේ පළමු මූලද්‍රව්‍යය අරා [] හි වත්මන් දර්ශකයේ ඇති මූලද්‍රව්‍යයට වඩා අඩු නම්, තොගයේ ඉහළින් ඇති යුගලය පොප් / මකන්න.
  5. තොගයේ විශාලත්වය 0 නොවේ නම්, පෙර විශාල මූලද්‍රව්‍ය අරා වල වත්මන් දර්ශකයේ අගය යුගලයේ දෙවන මූලද්‍රව්‍යය ලෙස යාවත්කාලීන කරන්න.
  6. අරාවෙහි [] සහ වත්මන් දර්ශකයේ වත්මන් දර්ශකයේ මූලද්‍රව්‍ය යුගලය සාදන්න. යුගලය තොගයේ තල්ලු කරන්න / ඇතුල් කරන්න.
  7. වර්ගයේ පූර්ණ සංඛ්‍යා යුගලවල තවත් තොගයක් සාදන්න.
  8. N-1 සිට 0 දක්වා ගමන් කර ඊළඟ විශාල මූලද්‍රව්‍ය අරාවේ වත්මන් දර්ශකයේ අගය වත්මන් දර්ශකය ලෙස සකසන්න. අට්ටාලය හිස් නොවන අතර, තොගයේ ඉහළින් ඇති යුගලයේ පළමු මූලද්‍රව්‍යය අරා [] හි වත්මන් දර්ශකයේ ඇති මූලද්‍රව්‍යයට වඩා අඩු නම්, තොගයේ ඉහළින් ඇති යුගලය පොප් / මකන්න.
  9. තොගයේ විශාලත්වය 0 නොවේ නම්, ඊළඟ විශාල මූලද්‍රව්‍ය අරාවේ වත්මන් දර්ශකයේ අගය යාවත්කාලීන කරන්න.
  10. අරාවෙහි [] සහ වත්මන් දර්ශකයේ වත්මන් දර්ශකයේ මූලද්‍රව්‍ය යුගලය සාදන්න. යුගලය තොගයේ තල්ලු කරන්න / ඇතුල් කරන්න.

කේතය

C ++ වැඩසටහන උපසිරැසි ගණනය කිරීම සඳහා ඉහළම ස්ථානයට පෙර දෙවන ඉහළම ස්ථානය පිහිටා ඇත

#include <iostream>
#include <stack>
#define MAXN 100005 
using namespace std; 
  
void makeNext(int arr[], int n, int nextBig[]){ 
    stack<pair<int, int> > s; 
  
    for(int i = n-1; i >= 0; i--){ 
  
        nextBig[i] = i; 
        while(!s.empty() && s.top().first < arr[i]){ 
            s.pop(); 
        }
  
        if(!s.empty()){ 
            nextBig[i] = s.top().second;
        }
  
        s.push(pair<int, int>(arr[i], i)); 
    } 
} 
  
void makePrev(int arr[], int n, int prevBig[]){ 
    stack<pair<int, int> > s; 
    
    for(int i = 0; i < n; i++){ 
  
        prevBig[i] = -1; 
        while(!s.empty() && s.top().first < arr[i]){ 
            s.pop(); 
        }
  
        if(!s.empty()){ 
            prevBig[i] = s.top().second; 
        }
  
        s.push(pair<int, int>(arr[i], i)); 
    } 
} 
  
int wrapper(int arr[], int n){ 
    int nextBig[MAXN]; 
    int prevBig[MAXN]; 
    int maxi[MAXN]; 
    int ans = 0; 
  
    makePrev(arr, n, prevBig); 
  
    makeNext(arr, n, nextBig); 
  
    for(int i = 0; i < n; i++){ 
        if (nextBig[i] != i){ 
            maxi[nextBig[i] - i] = max(maxi[nextBig[i] - i], i - prevBig[i]); 
        }
    }
  
    for(int i = 0; i < n; i++){ 
        ans += maxi[i]; 
    }
  
    return ans; 
} 
  
int main(){
    int a[] = { 1, 3, 2, 4 }; 
    int n = sizeof(a) / sizeof(a[0]);
    
    cout << wrapper(a, n) << endl; 
    
    return 0; 
}
3

ජාවා වැඩසටහන ඉහළම ස්ථානයට පෙර දෙවන ඉහළම ස්ථානය පිහිටා ඇති උප අරා ගණන් ගණනය කිරීම

import java.util.*; 
  
class CountSubarray{ 
      
    static int MAXN = 100005; 
      
    static class pair{  
        int first, second;
        
        public pair(int first, int second){  
            this.first = first;  
            this.second = second;  
        }  
    } 
    
    static void makeNext(int arr[], int n, int nextBig[]){ 
        Stack<pair> s = new Stack<>(); 
      
        for(int i = n-1; i >= 0; i--){ 
      
            nextBig[i] = i; 
            while(!s.empty() && s.peek().first < arr[i]){ 
                s.pop(); 
            }
      
            if(!s.empty()){ 
                nextBig[i] = s.peek().second; 
            }    
            
            s.push(new pair(arr[i], i)); 
        } 
    } 
      
    static void makePrev(int arr[], int n, int prevBig[]){ 
        Stack<pair> s = new Stack<>(); 
        
        for(int i = 0; i < n; i++){ 
      
            prevBig[i] = -1; 
            while(!s.empty() && s.peek().first < arr[i]){ 
                s.pop(); 
            }
      
            if(!s.empty()){ 
                prevBig[i] = s.peek().second; 
            }
      
            s.push(new pair(arr[i], i)); 
        } 
    } 
      
    static int wrapper(int arr[], int n){
        
        int []nextBig = new int[MAXN]; 
        int []prevBig = new int[MAXN]; 
        int []maxi = new int[MAXN]; 
        int ans = 0; 
      
        makePrev(arr, n, prevBig); 
      
        makeNext(arr, n, nextBig); 
      
        for(int i = 0; i < n; i++){ 
            if(nextBig[i] != i){ 
                maxi[nextBig[i] - i] = Math.max(maxi[nextBig[i] - i], i - prevBig[i]); 
            }
        }
      
        for(int i = 0; i < n; i++){ 
            ans += maxi[i]; 
        }
      
        return ans; 
    } 
      
    public static void main(String[] args){ 
      
        int a[] = { 1, 3, 2, 4 }; 
        int n = a.length; 
      
        System.out.println(wrapper(a, n)); 
    } 
}
3

සංකීර්ණ විශ්ලේෂණය

කාල සංකීර්ණත්වය

සාමාන්ය (n) මෙහි n යනු අරාවෙහි ඇති මූලද්‍රව්‍ය ගණන a []. අප ආදාන අරාව හරහා පමණක් ගමන් කර ඒවා තල්ලු කර හෝ තොගයෙන් ඉවත් කර ඇති බැවින්. කාල සංකීර්ණතාව රේඛීය වේ.

අභ්‍යවකාශ සංකීර්ණතාව

සාමාන්ය (n) අපි n මූලද්‍රව්‍ය සඳහා ඉඩ භාවිතා කළ නිසා. අපි ආදාන සිට මූලද්‍රව්‍ය තොගයට ගබඩා කර තැබුවෙමු. මූලද්‍රව්‍ය ගණන N වූ බැවින් අවකාශයේ සංකීර්ණතාව ද රේඛීය වේ.