அதிகபட்சத்திற்கு முன் இரண்டாவது மிக உயர்ந்த பொய்யான சப்ரேக்களை எண்ணுங்கள்


சிரமம் நிலை நடுத்தர
அடிக்கடி கேட்கப்படுகிறது ஹேக்கர் தரவரிசை
அணி ஸ்டேக்

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

“மிக உயர்ந்த இடத்தில் இரண்டாவது மிக உயர்ந்த பொய்யைக் கொண்டிருக்கும் சப்ரேக்களை எண்ணுங்கள்” என்ற சிக்கல் உங்களுக்கு வழங்கப்பட்டுள்ளது என்று கூறுகிறது வரிசை 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. தற்போதைய குறியீட்டில் ஒரு [] மற்றும் தற்போதைய குறியீட்டில் உள்ள உறுப்பு ஜோடியை உருவாக்குங்கள். ஜோடியை அடுக்கில் தள்ள / செருகவும்.
  7. வகை முழு எண் ஜோடிகளின் மற்றொரு அடுக்கை உருவாக்கவும்.
  8. N-1 முதல் 0 வரை பயணித்து அடுத்த பெரிய உறுப்பு வரிசையின் தற்போதைய குறியீட்டின் மதிப்பை தற்போதைய குறியீடாக அமைக்கவும். அடுக்கு காலியாக இல்லை மற்றும் அடுக்கின் மேற்புறத்தில் உள்ள ஜோடியிலிருந்து முதல் உறுப்பு வரிசை [] இல் உள்ள தற்போதைய குறியீட்டில் உள்ள உறுப்பைக் காட்டிலும் குறைவாக இருக்கும், அடுக்கின் மேல் ஜோடியை பாப் / நீக்கு.
  9. அடுக்கின் அளவு 0 இல்லையென்றால், அடுத்த பெரிய உறுப்பு வரிசையின் தற்போதைய குறியீட்டின் மதிப்பை அடுக்கின் மேற்புறத்தில் உள்ள ஜோடியிலிருந்து இரண்டாவது உறுப்பு என புதுப்பிக்கவும்.
  10. தற்போதைய குறியீட்டில் ஒரு [] மற்றும் தற்போதைய குறியீட்டில் உள்ள உறுப்பு ஜோடியை உருவாக்குங்கள். ஜோடியை அடுக்கில் தள்ள / செருகவும்.

குறியீடு

சி ++ நிரல் சப்ரேக்களை எண்ணும் இடத்தில் இரண்டாவது மிக உயர்ந்த இடத்தில் உள்ளது

#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 என்பது வரிசையில் உள்ள உறுப்புகளின் எண்ணிக்கை []. நாங்கள் உள்ளீட்டு வரிசைக்கு மேல் மட்டுமே பயணித்து அவற்றை தள்ளிவிட்டோம் அல்லது அவற்றை அடுக்கிலிருந்து அகற்றியுள்ளோம். நேர சிக்கலானது நேரியல்.

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

ஓ (n) ஏனென்றால் n உறுப்புகளுக்கு இடத்தைப் பயன்படுத்தினோம். உள்ளீட்டிலிருந்து உறுப்புகளை அடுக்கில் மட்டுமே சேமித்து வைத்திருந்தோம். உறுப்புகளின் எண்ணிக்கை N ஆக இருந்ததால், விண்வெளி சிக்கலானது நேரியல் ஆகும்.