उपनगराची मोजणी करा जिथे सर्वोच्चपेक्षा आधी सर्वात जास्त खोटे बोलले जाते


अडचण पातळी मध्यम
वारंवार विचारले हॅकररँक
अरे स्टॅक

समस्या विधान

“उपनगराची मोजणी करा जिथे सर्वोच्चपेक्षा आधी सर्वात जास्त खोटे बोलले जाते” असे नमूद करते की आपणास दिले गेले आहे अॅरे a [] आकाराचे n जेथे n पेक्षा जास्त किंवा समान आहे. सब सब्रेची एकूण संख्या मोजा ज्यामध्ये सबरायच्या सर्वोच्च घटकाची अनुक्रमणिका सब्रायच्या दुसर्‍या सर्वोच्च घटकाच्या निर्देशांकापेक्षा जास्त आहे.

उपनगराची मोजणी करा जिथे सर्वोच्चपेक्षा आधी सर्वात जास्त खोटे बोलले जाते

उदाहरण

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

अल्गोरिदम

  1. आकाराचा एनरे [a] आरंभ करा.
  2. तीन तयार करा अ‍ॅरे मागील मोठा घटक, पुढील मोठा घटक आणि अनुक्रमे जास्तीत जास्त घटक संचयित करण्यासाठी. उत्तर संग्रहित करण्यासाठी चल घोषित करा आणि त्याचे मूल्य 0 असे सेट करा.
  3. तयार स्टॅक प्रकार पूर्णांक च्या जोड्या.
  4. 0 ते एन -1 पर्यंत जा आणि मागील बिग एलिमेंट अ‍ॅरेच्या वर्तमान निर्देशांकाचे मूल्य -1 म्हणून सेट करा. स्टॅक रिक्त नसल्यास आणि स्टॅकच्या शीर्षस्थानी असलेल्या जोडीमधील पहिला घटक अ‍ॅरे ए []] मधील वर्तमान निर्देशांकातील घटकापेक्षा कमी असतो, परंतु स्टॅकच्या शीर्षस्थानी जोडी पॉप / हटवा.
  5. जर स्टॅकचा आकार 0 नसेल तर मागील मोठ्या घटक अ‍ॅरेच्या वर्तमान निर्देशांकाचे मूल्य स्टॅकच्या शीर्षस्थानी असलेल्या जोड्यांमधून दुसरे घटक म्हणून अद्यतनित करा.
  6. अ‍ॅरे [] आणि वर्तमान निर्देशांकामध्ये वर्तमान निर्देशांकावरील घटकांची जोडी तयार करा. स्टॅकमध्ये जोडी ढकलणे / घाला.
  7. पूर्णांक संख्येच्या जोड्यांचा आणखी एक स्टॅक तयार करा.
  8. एन -१ ते ० पर्यंत जा आणि पुढील मोठ्या घटक अ‍ॅरेच्या वर्तमान निर्देशांकाचे मूल्य वर्तमान अनुक्रमणिका म्हणून सेट करा. स्टॅक रिक्त नसल्यास आणि स्टॅकच्या शीर्षस्थानी असलेल्या जोडीमधील पहिला घटक अ‍ॅरे ए []] मधील वर्तमान निर्देशांकातील घटकापेक्षा कमी असतो, परंतु स्टॅकच्या शीर्षस्थानी जोडी पॉप / हटवा.
  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

गुंतागुंत विश्लेषण

वेळ कॉम्प्लेक्सिटी

O (n) जेथे एन अ‍ॅरे मधील घटकांची संख्या आहे []. आम्ही केवळ इनपुट अ‍ॅरेवरुन प्रवास केला आहे आणि त्यांना ढकलले किंवा त्यांना स्टॅकमधून काढले आहे. वेळेची जटिलता रेखीय असते.

स्पेस कॉम्प्लेक्सिटी

O (n) कारण आम्ही n घटकांसाठी जागा वापरली. आम्ही फक्त इनपुटमधील स्टॅकमध्ये घटक साठवत होतो. घटकांची संख्या एन असल्याने, अवकाश जटिलता देखील रेषात्मक आहे.