Пресметајте под-панели каде втората највисока лежи пред највисоката


Ниво на тешкотија Медиум
Често прашувано во ХакерРенк
Низа Магацинот

Изјава за проблем

Проблемот „Сметај ги под-палетите каде втората највисока лежи пред највисоката“ вели дека ти е даден низа a [] со големина n каде n е поголем или еднаков на 2. Брои го вкупниот број на под-низи во кои индексот на највисок елемент на под-низата е поголем од индексот на вториот највисок елемент на под-низата.

Пресметајте под-панели каде втората највисока лежи пред највисоката

пример

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

Алгоритам

  1. Иницијализира низа a [] со големина 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 е бројот на елементи во низата a []. Бидејќи само ја пребродивме низата за влез и ги турнавме или ги отстранивме од магацинот. Временската сложеност е линеарна.

Комплексноста на просторот

Тој) затоа што користевме простор за n елементи. Ние само ги чувавме елементите од влезот во оџакот. Бидејќи бројот на елементи беше N, комплексноста на просторот е исто така линеарна.