計算第二高位於最高前的子數組


難度級別
經常問 HackerRank
排列

問題陳述

問題“計算第二高在最高前的子數組”表明您被賦予了 排列 大小為n的a [],其中n大於或等於2。計算子數組最高元素的索引大於子數組第二高元素的索引的子數組總數。

計算第二高位於最高前的子數組

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

算法

  1. 初始化大小為n的數組a []。
  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

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,因此空間複雜度也是線性的。