दूसरी सबसे बड़ी झूठ जहां सबसे अधिक है, वहां गिनती को सुखाएं


कठिनाई स्तर मध्यम
में अक्सर पूछा HackerRank
ऐरे धुआँरा

समस्या का विवरण

समस्या "काउंट सबरेज़ जहां उच्चतम से पहले दूसरा सबसे बड़ा झूठ है" बताता है कि आपको ए सरणी [a] आकार n जहां n n 2 से अधिक या बराबर है। XNUMX. कुलियों की कुल संख्या की गणना करें जिसमें सबर्रे के उच्चतम तत्व का सूचकांक सबर्रे के दूसरे उच्चतम तत्व के सूचकांक से अधिक है।

दूसरी सबसे बड़ी झूठ जहां सबसे अधिक है, वहां गिनती को सुखाएं

उदाहरण

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

कलन विधि

  1. आकार n की एक सरणी [] को आरम्भ करें।
  2. तीन बनाएँ सरणियों पिछले बड़े तत्व, अगले बड़े तत्व और अधिकतम तत्व को क्रमशः स्टोर करने के लिए। उत्तर को स्टोर करने के लिए एक वैरिएबल की घोषणा करें और इसे 0 के रूप में सेट करें।
  3. बनाओ धुआँरा प्रकार पूर्णांक के जोड़े।
  4. 0 से n-1 तक के पार और पिछले बड़े तत्व सरणी के वर्तमान सूचकांक के मान को -1 के रूप में सेट करें। जबकि स्टैक खाली नहीं है और स्टैक के शीर्ष पर जोड़ी से पहला तत्व सरणी [a] में वर्तमान सूचकांक के तत्व से कम है, स्टैक के शीर्ष पर जोड़ी को पॉप / डिलीट करें।
  5. यदि स्टैक का आकार 0 नहीं है, तो स्टैक के शीर्ष पर जोड़े से दूसरे तत्व के रूप में पिछले बड़े तत्व सरणी के वर्तमान सूचकांक के मूल्य को अपडेट करें।
  6. एरे [a] और करंट इंडेक्स में करंट इंडेक्स में एलिमेंट की जोड़ी को बनाते हैं। स्टैक में जोड़ी को पुश / सम्मिलित करें।
  7. प्रकार पूर्णांक के जोड़े का एक और ढेर बनाएं।
  8. N-1 से 0 तक के पार और अगले बड़े तत्व सरणी के वर्तमान सूचकांक के मूल्य को वर्तमान सूचकांक के रूप में सेट करें। जबकि स्टैक खाली नहीं है और स्टैक के शीर्ष पर जोड़ी से पहला तत्व सरणी [a] में वर्तमान सूचकांक के तत्व से कम है, स्टैक के शीर्ष पर जोड़ी को पॉप / डिलीट करें।
  9. यदि स्टैक का आकार 0 नहीं है, तो स्टैक के शीर्ष पर जोड़े से दूसरे तत्व के रूप में अगले बड़े तत्व सरणी के वर्तमान सूचकांक के मूल्य को अपडेट करें।
  10. एरे [a] और करंट इंडेक्स में करंट इंडेक्स में एलिमेंट की जोड़ी को बनाते हैं। स्टैक में जोड़ी को पुश / सम्मिलित करें।

कोड

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 तत्वों के लिए स्थान का उपयोग किया है। हम केवल इनपुट से तत्वों को स्टैक में संग्रहीत कर रहे थे। चूंकि तत्वों की संख्या एन थी, इसलिए अंतरिक्ष जटिलता भी रैखिक है।