두 번째로 높은 부분이 가장 높은 부분보다 먼저있는 부분 배열을 계산


난이도 중급
자주 묻는 질문 HackerRank
배열 스택

문제 정책

"가장 높은 값보다 두 번째로 높은 부분이있는 부분 배열을 세 어라"라는 문제는 정렬 크기 n의 a [] 여기서 n은 2보다 크거나 같습니다. 하위 배열의 가장 높은 요소의 인덱스가 하위 배열의 두 번째로 높은 요소의 인덱스보다 큰 전체 하위 배열의 수를 계산합니다.

두 번째로 높은 부분이 가장 높은 부분보다 먼저있는 부분 배열을 계산

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

암호알고리즘

  1. n 크기의 배열 a []를 초기화합니다.
  2. XNUMX 개 만들기 배열 이전 큰 요소, 다음 큰 요소 및 최대 요소를 각각 저장합니다. 답을 저장할 변수를 선언하고 그 값을 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

두 번째로 높은 부분이 가장 높은 부분보다 먼저있는 부분 배열을 계산하는 Java 프로그램

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) 여기서 n은 배열 a []의 요소 수입니다. 입력 배열을 탐색하고 밀어 넣거나 스택에서 제거했기 때문입니다. 시간 복잡도는 선형입니다.

공간 복잡성

O (N) n 개의 요소에 공간을 사용했기 때문입니다. 입력의 요소 만 스택에 저장했습니다. 요소의 수가 N이므로 공간 복잡성도 선형입니다.