সাববারে গণনা করুন যেখানে সর্বোচ্চের আগে দ্বিতীয় সর্বোচ্চ থাকে


কাঠিন্য মাত্রা মধ্যম
প্রায়শই জিজ্ঞাসা করা হয় HackerRank
বিন্যাস গাদা

সমস্যা বিবৃতি

সমস্যা "সাববারাই গণনা করুন যেখানে সর্বোচ্চের আগে দ্বিতীয় সর্বোচ্চ মিথ্যা" উল্লেখ করে যে আপনাকে একটি দেওয়া হয়েছে বিন্যাস a [] আকারের n যেখানে n এর চেয়ে বড় বা সমান 2 sub সাববারির মোট সংখ্যাটি গণনা করুন যেখানে সুব্রয়ের সর্বোচ্চ উপাদানটির সূচকটি সুবরের দ্বিতীয় সর্বোচ্চ উপাদানটির সূচকের চেয়ে বেশি।

সাববারে গণনা করুন যেখানে সর্বোচ্চের আগে দ্বিতীয় সর্বোচ্চ থাকে

উদাহরণ

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

অ্যালগরিদম

  1. আকারের একটি অ্যারে [[] অ্যারের সূচনা করুন।
  2. তিনটি তৈরি করুন অ্যারে পূর্ববর্তী বড় উপাদান, পরবর্তী বড় উপাদান এবং সর্বোচ্চ উপাদান যথাক্রমে সংরক্ষণ করতে। উত্তর সঞ্চয় করতে একটি ভেরিয়েবল ঘোষণা করুন এবং এর মান 0 হিসাবে নির্ধারণ করুন।
  3. একটা তৈরি কর গাদা টাইপ পূর্ণসংখ্যার জোড়া।
  4. 0 থেকে এন -1 এ ট্র্যাভার করুন এবং পূর্ববর্তী বড় উপাদানগুলির অ্যারের বর্তমান সূচকের মান -1 হিসাবে সেট করুন। স্ট্যাকটি খালি নয় এবং স্ট্যাকের শীর্ষে জোড়া থেকে প্রথম উপাদানটি অ্যারে এ []] এর বর্তমান সূচকের উপাদানের চেয়ে কম তবে স্ট্যাকের শীর্ষে জুটিটি পপ / মুছুন।
  5. স্ট্যাকের আকার 0 না হলে, স্ট্যাকের শীর্ষে জোড়া থেকে দ্বিতীয় উপাদান হিসাবে পূর্বের বড় উপাদান অ্যারের বর্তমান সূচকের মান আপডেট করুন।
  6. অ্যারে এ []] এবং বর্তমান সূচকে বর্তমান সূচীতে উপাদানটির জুটি তৈরি করুন। স্ট্যাকের মধ্যে জোড়টি পুশ / sertোকান।
  7. পূর্ণসংখ্যার জোড়গুলির আরও একটি স্ট্যাক তৈরি করুন।
  8. N-1 থেকে 0 অবধি অনুসরণ করুন এবং পরবর্তী বড় উপাদান অ্যারের বর্তমান সূচককে বর্তমান সূচক হিসাবে সেট করুন। স্ট্যাকটি খালি নয় এবং স্ট্যাকের শীর্ষে জোড়া থেকে প্রথম উপাদানটি অ্যারে এ []] এর বর্তমান সূচকের উপাদানের চেয়ে কম তবে স্ট্যাকের শীর্ষে জুটিটি পপ / মুছুন।
  9. স্ট্যাকের আকার 0 না হলে স্ট্যাকের শীর্ষে জোড় থেকে দ্বিতীয় উপাদান হিসাবে পরবর্তী বড় উপাদান অ্যারের বর্তমান সূচকের মান আপডেট করুন।
  10. অ্যারে এ []] এবং বর্তমান সূচকে বর্তমান সূচীতে উপাদানটির জুটি তৈরি করুন। স্ট্যাকের মধ্যে জোড়টি পুশ / sertোকান।

কোড

সি ++ প্রোগ্রাম সাববারে গণনা করার জন্য যেখানে সর্বোচ্চের চেয়ে দ্বিতীয় সর্বোচ্চ থাকে

#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

জাভা প্রোগ্রাম সাবহারিকে গণনা করতে যেখানে সর্বোচ্চের চেয়ে দ্বিতীয় বৃহত্তম lie

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

জটিলতা বিশ্লেষণ

সময় জটিলতা

উপর) যেখানে এন অ্যারেতে উপাদানগুলির সংখ্যা a []। যেহেতু আমরা কেবল ইনপুট অ্যারে পেরিয়েছি এবং তাদের ধাক্কা দিয়েছি বা স্ট্যাক থেকে সরিয়েছি। সময় জটিলতা রৈখিক।

স্পেস জটিলতা ity

উপর) কারণ আমরা n উপাদানগুলির জন্য স্থান ব্যবহার করেছি। আমরা কেবল স্ট্যাকের ইনপুট থেকে উপাদানগুলি সংরক্ষণ করছিলাম। যেহেতু উপাদানগুলির সংখ্যা ছিল এন, তাই স্থান জটিলতাও লিনিয়ার।