ከከፍተኛው በፊት በሁለተኛ ደረጃ የሚተኛበትን ንዑስ ቤቶችን ይ Countጥሩ


የችግር ደረጃ መካከለኛ
ውስጥ በተደጋጋሚ ተጠየቀ HackerRank
ሰልፍ ክምር

የችግሩ መግለጫ

ችግሩ “ከከፍተኛው በሁለተኛ ደረጃ በሚተኛበት ቦታ ያሉ subarrays ን ይቆጥሩ” አንድ እንደተሰጠዎት ይናገራል ደርድር አንድ n] n የሚበልጥበት ወይም የሚበልጥበት ቦታ። 2. የከፊል ንዑስ ክፍል ማውጫ ከሁለተኛው ከፍተኛ ንዑስ ክፍል መረጃ ጠቋሚ የሚበልጥበትን አጠቃላይ ንዑስ አደረጃጀቶች ብዛት ይቁጠሩ።

ከከፍተኛው በፊት በሁለተኛ ደረጃ የሚተኛበትን ንዑስ ቤቶችን ይ Countጥሩ

ለምሳሌ

 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. በድርድር አንድ [] እና አሁን ባለው መረጃ ጠቋሚ ላይ የአሁኑን ንጥረ ነገር ጥንድ ይፍጠሩ። ጥንድውን በቁልል ውስጥ ይግፉ / ያስገቡ ፡፡

ኮድ

ሲ ++ መርሃግብሩ ከከፍተኛው በፊት ሁለተኛ ከፍተኛ ደረጃ ላይ የሚገኙትን subarrays ለመቁጠር ፕሮግራም

#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 ስለነበረ ፣ የቦታ ውስብስብነቱ እንዲሁ መስመራዊ ነው።