ນັບ subarrays ບ່ອນທີ່ນອນທີ່ສູງທີ່ສຸດອັນດັບສອງກ່ອນທີ່ສູງທີ່ສຸດ


ລະດັບຄວາມຫຍຸ້ງຍາກ ຂະຫນາດກາງ
ຖາມເລື້ອຍໆໃນ ແຮກເກີຣ
Array Stack

ຖະແຫຼງການບັນຫາ

ບັນຫາ "ນັບ subarrays ບ່ອນທີ່ນອນທີ່ສູງທີ່ສຸດຄັ້ງທີສອງກ່ອນທີ່ສູງທີ່ສຸດ" ລະບຸວ່າທ່ານໄດ້ຮັບ array a [] ຂອງຂະ ໜາດ n ບ່ອນທີ່ n ໃຫຍ່ກ່ວາຫຼືເທົ່າກັບ 2. ນັບ ຈຳ ນວນທັງ ໝົດ ຂອງ subarrays ທີ່ດັດສະນີຂອງອົງປະກອບທີ່ສູງທີ່ສຸດຂອງ subarray ແມ່ນໃຫຍ່ກວ່າດັດຊະນີຂອງອົງປະກອບທີ່ສູງທີ່ສຸດອັນດັບສອງຂອງ subarray.

ນັບ subarrays ບ່ອນທີ່ນອນທີ່ສູງທີ່ສຸດອັນດັບສອງກ່ອນທີ່ສູງທີ່ສຸດ

ຍົກຕົວຢ່າງ

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

ລະບົບວິເຄາະ

  1. ເລີ່ມຕົ້ນຂບວນ a [] ຂອງຂະ ໜາດ n.
  2. ສ້າງສາມ ອາຄານ ການເກັບຮັກສາອົງປະກອບໃຫຍ່ທີ່ຜ່ານມາ, ອົງປະກອບໃຫຍ່ຕໍ່ໄປແລະອົງປະກອບສູງສຸດຕາມ ລຳ ດັບ. ປະກາດຕົວແປເພື່ອເກັບ ຄຳ ຕອບແລະຕັ້ງຄ່າໃຫ້ເປັນ 0.
  3. ສ້າງເປັນ stack ຄູ່ຂອງ ຈຳ ນວນປະເພດ.
  4. Traverse ຈາກ 0 ເຖິງ n-1 ແລະ ກຳ ນົດມູນຄ່າຂອງດັດຊະນີປັດຈຸບັນຂອງອາເລອົງປະກອບໃຫຍ່ກ່ອນ ໜ້າ ນີ້ເປັນ -1. ໃນຂະນະທີ່ stack ບໍ່ແມ່ນວ່າງແລະອົງປະກອບ ທຳ ອິດຈາກຄູ່ຢູ່ເທິງສຸດຂອງ stack ແມ່ນ ໜ້ອຍ ກວ່າອົງປະກອບທີ່ຢູ່ໃນດັດຊະນີປັດຈຸບັນໃນ array a [], pop / ລົບຄູ່ທີ່ຢູ່ເທິງສຸດຂອງ stack.
  5. ຖ້າຫາກວ່າຂະ ໜາດ ຂອງ stack ບໍ່ແມ່ນ 0, ປັບປຸງມູນຄ່າຂອງດັດຊະນີປັດຈຸບັນຂອງ array ທີ່ໃຫຍ່ກ່ອນ ໜ້າ ນີ້ເປັນອົງປະກອບທີສອງຈາກຄູ່ຢູ່ເທິງສຸດຂອງ stack.
  6. ປະກອບຄູ່ຂອງອົງປະກອບທີ່ດັດສະນີປັດຈຸບັນໃນ array a ແລະດັດຊະນີປັດຈຸບັນ. ຍູ້ / ໃສ່ຄູ່ໃນ stack.
  7. ສ້າງຊຸດຄູ່ອີກ ຈຳ ນວນຄູ່ຂອງ ຈຳ ນວນປະເພດ.
  8. Traverse ຈາກ n-1 ເຖິງ 0 ແລະກໍານົດມູນຄ່າຂອງດັດຊະນີປັດຈຸບັນຂອງອາໄລ່ອົງປະກອບໃຫຍ່ຕໍ່ໄປເປັນດັດຊະນີປັດຈຸບັນ. ໃນຂະນະທີ່ stack ບໍ່ແມ່ນວ່າງແລະອົງປະກອບ ທຳ ອິດຈາກຄູ່ຢູ່ເທິງສຸດຂອງ stack ແມ່ນ ໜ້ອຍ ກວ່າອົງປະກອບທີ່ຢູ່ໃນດັດຊະນີປັດຈຸບັນໃນ array a [], pop / ລົບຄູ່ທີ່ຢູ່ເທິງສຸດຂອງ stack.
  9. ຖ້າຫາກວ່າຂະ ໜາດ ຂອງ stack ບໍ່ແມ່ນ 0, ປັບປຸງມູນຄ່າຂອງດັດຊະນີປັດຈຸບັນຂອງ array ຂະ ໜາດ ໃຫຍ່ຕໍ່ໄປເປັນອົງປະກອບທີສອງຈາກຄູ່ຢູ່ເທິງສຸດຂອງ stack.
  10. ປະກອບຄູ່ຂອງອົງປະກອບທີ່ດັດສະນີປັດຈຸບັນໃນ array a ແລະດັດຊະນີປັດຈຸບັນ. ຍູ້ / ໃສ່ຄູ່ໃນ stack.

ລະຫັດ

C ++ Program ເພື່ອນັບ 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 Program ເພື່ອນັບ 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 []. ເນື່ອງຈາກວ່າພວກເຮົາຫາກໍ່ຜ່ານພຽງແຕ່ຂີດຂວາງການປ້ອນຂໍ້ມູນແລະຍູ້ພວກມັນຫຼືເອົາພວກມັນອອກຈາກ stack. ຄວາມສັບສົນຂອງເວລາແມ່ນເປັນເສັ້ນ.

ຄວາມສັບສົນໃນອະວະກາດ

O (n) ເນື່ອງຈາກວ່າພວກເຮົາໃຊ້ພື້ນທີ່ ສຳ ລັບອົງປະກອບ n. ພວກເຮົາພຽງແຕ່ເກັບຮັກສາອົງປະກອບຕ່າງໆຈາກການປ້ອນຂໍ້ມູນເຂົ້າໃນຊັ້ນ. ເນື່ອງຈາກ ຈຳ ນວນຂອງອົງປະກອບແມ່ນ N, ຄວາມສັບສົນຂອງພື້ນທີ່ຍັງເປັນເສັ້ນ.