ഏറ്റവും ഉയർന്നതിന് മുമ്പുള്ള രണ്ടാമത്തെ ഉയർന്ന കിടക്കുന്ന സബ്‌റേകളുടെ എണ്ണം


വൈഷമ്യ നില മീഡിയം
പതിവായി ചോദിക്കുന്നു ഹാക്കർ റാങ്ക്
അറേ കൂനകൂട്ടുക

പ്രശ്നം പ്രസ്താവന

“ഏറ്റവും ഉയർന്നതിന് മുമ്പുള്ള രണ്ടാമത്തെ ഉയർന്ന കിടപ്പ് ഉള്ള സബ്‌റേകളുടെ എണ്ണം” എന്ന പ്രശ്നം നിങ്ങൾക്ക് ഒരു നൽകിയിട്ടുണ്ടെന്ന് പറയുന്നു ശ്രേണി a [] വലിപ്പം n, ഇവിടെ n 2 നെക്കാൾ വലുതോ തുല്യമോ ആണ്. സബാരെയുടെ ഏറ്റവും ഉയർന്ന മൂലകത്തിന്റെ സൂചിക സബ്‌റെയുടെ രണ്ടാമത്തെ ഉയർന്ന മൂലകത്തിന്റെ സൂചികയേക്കാൾ കൂടുതലുള്ള മൊത്തം സബ്‌റേകളുടെ എണ്ണം കണക്കാക്കുക.

ഏറ്റവും ഉയർന്നതിന് മുമ്പുള്ള രണ്ടാമത്തെ ഉയർന്ന കിടക്കുന്ന സബ്‌റേകളുടെ എണ്ണം

ഉദാഹരണം

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

അൽഗോരിതം

  1. വലുപ്പം n ന്റെ [] ഒരു അറേ സമാരംഭിക്കുക.
  2. മൂന്ന് സൃഷ്ടിക്കുക ശ്രേണികൾ മുമ്പത്തെ വലിയ ഘടകം, അടുത്ത വലിയ ഘടകം, പരമാവധി ഘടകം എന്നിവ യഥാക്രമം സംഭരിക്കുന്നതിന്. ഉത്തരം സംഭരിക്കുന്നതിന് ഒരു വേരിയബിൾ പ്രഖ്യാപിച്ച് അതിന്റെ മൂല്യം 0 ആയി സജ്ജമാക്കുക.
  3. സൃഷ്ടിക്കുക സ്റ്റാക്ക് ടൈപ്പ് ഇൻറിജറിന്റെ ജോഡികളുടെ.
  4. 0 മുതൽ n-1 വരെ സഞ്ചരിച്ച് മുമ്പത്തെ വലിയ ഘടക അറേയുടെ നിലവിലെ സൂചികയുടെ മൂല്യം -1 ആയി സജ്ജമാക്കുക. സ്റ്റാക്ക് ശൂന്യമല്ലെങ്കിലും സ്റ്റാക്കിന്റെ മുകളിലുള്ള ജോഡിയിൽ നിന്നുള്ള ആദ്യ ഘടകം അറേ [] ലെ നിലവിലെ സൂചികയിലെ ഘടകത്തേക്കാൾ കുറവാണെങ്കിൽ, സ്റ്റാക്കിന് മുകളിലുള്ള ജോഡി പോപ്പ് / ഇല്ലാതാക്കുക.
  5. സ്റ്റാക്കിന്റെ വലുപ്പം 0 അല്ലെങ്കിൽ, മുമ്പത്തെ വലിയ ഘടക അറേയുടെ നിലവിലെ സൂചികയുടെ മൂല്യം സ്റ്റാക്കിന്റെ മുകളിലുള്ള ജോഡിയിൽ നിന്നുള്ള രണ്ടാമത്തെ ഘടകമായി അപ്‌ഡേറ്റുചെയ്യുക.
  6. അറേ a [] ലെ നിലവിലെ സൂചികയിലും നിലവിലെ സൂചികയിലും മൂലകത്തിന്റെ ജോഡി രൂപപ്പെടുത്തുക. ജോഡി സ്റ്റാക്കിൽ പുഷ് ചെയ്യുക / ചേർക്കുക.
  7. ടൈപ്പ് ഇൻറിജറിന്റെ ജോഡികളുടെ മറ്റൊരു സ്റ്റാക്ക് സൃഷ്ടിക്കുക.
  8. N-1 മുതൽ 0 വരെ സഞ്ചരിച്ച് അടുത്ത വലിയ ഘടക അറേയുടെ നിലവിലെ സൂചികയുടെ മൂല്യം നിലവിലെ സൂചികയായി സജ്ജമാക്കുക. സ്റ്റാക്ക് ശൂന്യമല്ലെങ്കിലും സ്റ്റാക്കിന്റെ മുകളിലുള്ള ജോഡിയിൽ നിന്നുള്ള ആദ്യ ഘടകം അറേ [] ലെ നിലവിലെ സൂചികയിലെ ഘടകത്തേക്കാൾ കുറവാണെങ്കിൽ, സ്റ്റാക്കിന് മുകളിലുള്ള ജോഡി പോപ്പ് / ഇല്ലാതാക്കുക.
  9. സ്റ്റാക്കിന്റെ വലുപ്പം 0 അല്ലെങ്കിൽ, അടുത്ത വലിയ എലമെൻറ് അറേയുടെ നിലവിലെ സൂചികയുടെ മൂല്യം സ്റ്റാക്കിന്റെ മുകളിലുള്ള ജോഡിയിൽ നിന്നുള്ള രണ്ടാമത്തെ ഘടകമായി അപ്‌ഡേറ്റ് ചെയ്യുക.
  10. അറേ a [] ലെ നിലവിലെ സൂചികയിലും നിലവിലെ സൂചികയിലും മൂലകത്തിന്റെ ജോഡി രൂപപ്പെടുത്തുക. ജോഡി സ്റ്റാക്കിൽ പുഷ് ചെയ്യുക / ചേർക്കുക.

കോഡ്

ഏറ്റവും ഉയർന്നതിന് മുമ്പുള്ള രണ്ടാമത്തെ ഉയർന്ന സബ്‌റേകൾ എണ്ണുന്നതിനുള്ള സി ++ പ്രോഗ്രാം

#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

സങ്കീർണ്ണത വിശകലനം

സമയ സങ്കീർണ്ണത

O (n) ഇവിടെ n എന്നത് അറേയിലെ മൂലകങ്ങളുടെ എണ്ണം a []. ഞങ്ങൾ‌ ഇൻ‌പുട്ട് അറേയിലൂടെ സഞ്ചരിച്ച് അവയെ തള്ളുകയോ സ്റ്റാക്കിൽ‌ നിന്നും നീക്കം ചെയ്യുകയോ ചെയ്‌തതിനാൽ‌. സമയ സങ്കീർണ്ണത രേഖീയമാണ്.

ബഹിരാകാശ സങ്കീർണ്ണത

O (n) കാരണം n ഘടകങ്ങൾക്ക് ഞങ്ങൾ ഇടം ഉപയോഗിച്ചു. ഇൻപുട്ടിൽ നിന്നുള്ള ഘടകങ്ങൾ ഞങ്ങൾ സ്റ്റാക്കിലേക്ക് സംഭരിക്കുകയായിരുന്നു. മൂലകങ്ങളുടെ എണ്ണം N ആയതിനാൽ, സ്ഥല സങ്കീർണ്ണതയും രേഖീയമാണ്.