นับ subarrays ที่สูงสุดรองลงมาก่อนสูงสุด


ระดับความยาก กลาง
ถามบ่อยใน HackerRank
แถว กอง

คำชี้แจงปัญหา

ปัญหา“ นับ subarrays ที่อันดับรองลงมาก่อนสูงสุด” ระบุว่าคุณได้รับไฟล์ แถว a [] ของขนาด n โดยที่ n มากกว่าหรือเท่ากับ 2 ให้นับจำนวน subarray ทั้งหมดที่ดัชนีขององค์ประกอบสูงสุดของ subarray มากกว่าดัชนีขององค์ประกอบสูงสุดอันดับสองของ subarray

นับ subarrays ที่สูงสุดรองลงมาก่อนสูงสุด

ตัวอย่าง

 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 ++ เพื่อนับ 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

โปรแกรม Java เพื่อนับ subarrays ที่อยู่สูงสุดเป็นอันดับสองก่อนสูงสุด

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 ความซับซ้อนของพื้นที่จึงเป็นเส้นตรงด้วย