subarrays အားလုံး၏အနိမ့်ဆုံးနှင့်အမြင့်ဆုံး element မ်ား k


ခက်ခဲအဆင့် ခိုင်မာသော
မကြာခဏမေးတယ် ByteDance Capital One ကူပွန် Databricks Google Twilio Yandex
အခင်းအကျင်း ဆံပင်ကြိုး လျှော Window

ပြProbleနာဖော်ပြချက်

ပြproblemနာ“ အရွယ်အစား k ၏ subarrays အားလုံး၏အနိမ့်ဆုံးနှင့်အမြင့်ဆုံးဒြပ်စင်များစုစုပေါင်း” သည်သင့်အားအပြုသဘောဆောင်ခြင်းနှင့်အနှုတ်လက္ခဏာများပါသောခင်းကျင်းခြင်းတစ်ခုပေးထားသည်။ အရွယ်အစား k ၏အရွယ်အစားအနိမ့်ဆုံးနှင့်အမြင့်ဆုံးပမာဏကိုရှာရန်ဖော်ပြသည်။

ဥပမာ

arr[] = {5, 9, 8, 3, -4, 2, 1, -5}
k = 4
17

ရှင်းလင်းချက်
အရွယ်အစား 4 အရွယ်အစားခွဲခွဲအားလုံးသည်၊
{5, 9, 8, 3}: min + max = 9 + 3 = 12
{9, 8, 3, -4}: min + max = -4 + 9 = 5
{8, 3, -4, 2}: min + max = -4 + 8 = 4
{3, -4, 2, 1}: min + max = -4 + 3 = -1
{-4, 2, 1, -5}: min + max = -5 + 2 = -3

subarrays အားလုံး၏အနိမ့်ဆုံးနှင့်အမြင့်ဆုံး element မ်ား k

arr[] = {1, -1, 2, -2, 3, -3}
k = 2
2

ရှင်းလင်းချက်
အရွယ်အစား 2 အရွယ်အစားခွဲခွဲအားလုံးသည်၊
{1, -1}: min + max = -1 + 1 = 0
{-1, 2}: min + max = -1 + 2 = 1
{2, -2}: min + max = -2 + 2 = 0
{-2, 3}: min + max = -2 + 3 = 1
{3, -3}: min + max = -3 + 3 = 0

ချဉ်းကပ်နည်း

နုံချဉ်းကပ်နည်း

အနိမ့်ဆုံးနှင့်အမြင့်ဆုံးဒြပ်စင်များကိုရှာ။ ပေါင်းလဒ်ကို print ထုတ်ရန် k အရွယ်ရှိ k အရွယ်အစားငယ်များ၏လမ်းကြောင်းကိုဖြတ်သွားပါ။

  1. ကိန်းရှင်တစ်ခုကို 0 အဖြစ်စတင်ပါ။
  2. i သည် 0 မှ (n - k) နှင့်ညီမျှသောကွင်းဆက်တစ်ခုဖွင့်ပါ။ ထို n တွင်ပေးထားသောဒြပ်စင်၏စုစုပေါင်းအရေအတွက်ဖြစ်သည် အခင်းအကျင်း။ i တစ်ခုချင်းစီသည်အရွယ်အစား k ၏ sub-ခင်းကျင်းမှု၏အစမှတ်အဖြစ်ဆောင်ရွက်သည်။
  3. j = i to (i + k) to nested loop တစ်ခုကိုဖွင့်ပါ (မပါ ၀ င်ပါ။ ) ဤကွင်းဆက်သည်အရွယ်အစား k ၏ sub-array ကိုကိုယ်စားပြုသည်။ ဒီ sub-ခင်းကျင်းဖြတ်ပြီးနိမ့်ဆုံးနှင့်အမြင့်ဆုံးဒြပ်စင်ကိုရှာဖွေ, ဤအသီးသီး min နှင့် max ဖြစ်ကုန်အံ့။
  4. ပေါင်းလဒ် (min + max) ထည့်ပါ။
  5. အဆိုပါဖြတ်သန်း၏အဆုံးမှာပြန်လာပေါင်းလဒ်။

ဘယ်မှာ n ကပေးထားတဲ့ခင်းကျင်းထဲမှာစုစုပေါင်းဒြပ်စင်အရေအတွက်ဖြစ်ပါတယ်။

subarrays အားလုံး၏အနိမ့်ဆုံးနှင့်အမြင့်ဆုံး element များ၏စုစုပေါင်းကိုရှာရန် Java Code k

class SumOfMinimumAndMaximumElementsOfAllSubarraysOfSizeK {
    private static int sumOfMinMax(int[] arr, int k) {
        int n = arr.length;
        // initialize sum as 0
        int sum = 0;

        // Traverse all the subarray of size k one by one
        for (int i = 0; i <= n - k; i++) {
            int min = Integer.MAX_VALUE;
            int max = Integer.MIN_VALUE;
            // traverse the current subarray and find the min and max
            for (int j = i; j < i + k; j++) {
                min = Math.min(min, arr[j]);
                max = Math.max(max, arr[j]);
            }

            // add (min + max) to the sum
            sum += (min + max);
        }

        return sum;
    }

    public static void main(String[] args) {
        // Example 1
        int arr1[] = new int[]{5, 9, 8, 3, -4, 2, 1, -5};
        int k1 = 4;
        System.out.println(sumOfMinMax(arr1, k1));

        // Example 2
        int arr2[] = new int[]{1, -1, 2, -2, 3, -3};
        int k2 = 2;
        System.out.println(sumOfMinMax(arr2, k2));
    }
}
17
2

C ++ ၏ subarrays အားလုံး၏အနိမ့်ဆုံးနှင့်အများဆုံး element မ်ား၏စုစုပေါင်းကိုရှာဖွေရန်ကုဒ် k

#include<bits/stdc++.h> 
using namespace std; 

int sumOfMinMax(int *arr, int k, int n) {
    // initialize sum as 0
    int sum = 0;
    
    // Traverse all the subarray of size k one by one
    for (int i = 0; i <= (n - k); i++) {
        int min = INT_MAX;
        int max = INT_MIN;
        // traverse the current subarray and find the min and max
        for (int j = i; j < i + k; j++) {
            min = std::min(min, arr[j]);
            max = std::max(max, arr[j]);
        }
        
        // add (min + max) to the sum
        sum += (min + max);
    }
    
    return sum;
}

int main() {
    // Example 1
    int arr1[] = {5, 9, 8, 3, -4, 2, 1, -5};
    int k1 = 4;
    cout<<sumOfMinMax(arr1, k1, sizeof(arr1) / sizeof(arr1[0]))<<endl;

    // Example 2
    int arr2[] = {1, -1, 2, -2, 3, -3};
    int k2 = 2;
    cout<<sumOfMinMax(arr2, k2, sizeof(arr2) / sizeof(arr2[0]))<<endl;
    
    return 0;
}
17
2

ရှုပ်ထွေးဆန်းစစ်ခြင်း

အချိန်ရှုပ်ထွေး = အို (n * k)
အာကာသရှုပ်ထွေးမှု = အို (၁)

ဤတွင်အချိန်ရှုပ်ထွေးမှုသည် polynomial ဖြစ်သည်။ အဘယ်ကြောင့်ဆိုသော်ကျွန်ုပ်တို့သည် sub-array တစ်ခုချင်းစီအတွက်ပြtheနာကိုကျွန်ုပ်တို့သီးခြားလွတ်လပ်စွာဖြေရှင်းခြင်းဖြစ်သည်။ ကျွန်ုပ်တို့သည်သာသိုလှောင်ထားသည်။ y နှင့်အနိမ့်ဆုံးအနိမ့်ဆုံးအတွက်နှစ်ကိန်းရှင်လိုအပ်သောနေရာသည်အမြဲတမ်းဖြစ်သည်။

အကောင်းဆုံးချဉ်းကပ်နည်း

နှစ်ခုဖန်တီးပါ Deque d1 နှင့် d2 နှစ်ခုစလုံးတွင် deques နှစ်ခုစလုံးသည် sub-array ၏အနည်းဆုံးနှင့်အမြင့်ဆုံးဖြစ်စေနိုင်သည့် element များ၏ညွှန်းကိန်းကိုသိုလှောင်သည်။ Deque d1 တွင်ဒြပ်စင်ပါ ၀ င်ပြီးရှေ့မှသည်နောက်မှအစဉ်လိုက်ကျဆင်းသည်။

  1. Variable sum ကို 0. အဖြစ်စတင်ပါ။ deques d1 နှင့် d2 နှစ်ခုကိုဖန်တီးပါ။ အရွယ်အစား k ၏ပထမခွဲပုဒ်ကိုစဉ်းစားပါ။
  2. လက်ရှိအရွယ်အစား k ၏ sub-ခင်းကျင်းမှု၏ဒြပ်ထုသည် d1 ၏အနောက်ဘက်နောက်ဘက်ရှိဒြပ်စင်ထက်ကြီးသည်သို့မဟုတ်တန်းတူဖြစ်သော်လည်း Deque d1 ၏နောက်ဘက် element ကိုဖယ်ရှားပါ။
  3. လက်ရှိအရွယ်အစား k ၏ sub-ခင်းကျင်းမှု၏ဒြပ်စင်သည် d2 ၏အနောက်ဘက်နောက်ဘက်ရှိဒြပ်စင်ထက်ငယ်သည်သို့မဟုတ်တန်းတူဖြစ်သော်လည်း Deque d2 ၏နောက်ဘက် element ကိုဖယ်ရှားပါ။
  4. နှစ် ဦး စလုံး deques ၏နောက်ဘက်မှလက်ရှိအညွှန်းကိန်းထည့်ပါ။
  5. Deque of dque d1 သည် sub- ခင်းကျင်း၏အမြင့်ဆုံးဒြပ်စင်အညွှန်းဖြစ်ပြီး deque d2 ၏နောက်ဘက်သည် sub-array ၏နိမ့်ဆုံးသောအညွှန်းဖြစ်သည်။ Variable sum သို့အမြင့်ဆုံးနှင့်နိမ့်ဆုံး element ကိုပေါင်းထည့်ပါ။
  6. ကျန်ရှိနေသေးသော sub-arrays များကိုအရွယ်အစား k ကိုဖြတ်ပြီးအဆင့် ၂ မှ ၅ ကိုပြန်လုပ်ပါ။ ကျန်ရှိနေသေးသော sub-arrays များအားလုံးကိုအသုံးပြုပါ လျှောပြတင်းပေါက် technique ကို ယခင် sub-array တွင်မပါရှိသော element ကိုသာလုပ်ဆောင်ပါ။
  7. sub-arrays များအားလုံးကိုဖြတ်ပြီးတဲ့အခါ၊ sum sum ကိုပြန်သွားပါ။

subarrays အားလုံး၏အနည်းဆုံးနှင့်အမြင့်ဆုံးပမာဏကိုရှာရန် Java ကုဒ် k

import java.util.Deque;
import java.util.LinkedList;

class SumOfMinimumAndMaximumElementsOfAllSubarraysOfSizeK {
    private static int sumOfMinMax(int[] arr, int k) {
        int n = arr.length;
        // initialize sum as 0
        int sum = 0;

        // create 2 deques d1 and d2
        Deque<Integer> d1 = new LinkedList<>();
        Deque<Integer> d2 = new LinkedList<>();

        // first subarray
        for (int i = 0; i < k; i++) {
            // only push the elements that may contribute to maximum
            while (!d1.isEmpty() && arr[d1.peekLast()] <= arr[i])
                d1.removeLast();

            // only push the elements that may contribute to minimum
            while (!d2.isEmpty() && arr[d2.peekLast()] >= arr[i])
                d2.removeLast();

            // add the current elememt's index
            d1.addLast(i);
            d2.addLast(i);
        }

        // sum of min and max for first subarray
        sum += arr[d2.peekFirst()] + arr[d1.peekFirst()];

        // traverse the remaining subarray
        for (int i = k; i < n; i++) {
            // remove the previous element (sliding window technique)
            while (!d2.isEmpty() && d2.peekFirst() <= i - k)
                d2.removeFirst();
            while (!d1.isEmpty() && d1.peekFirst() <= i - k)
                d1.removeFirst();

            // only push the elements that may contribute to maximum
            while (!d1.isEmpty() && arr[d1.peekLast()] <= arr[i])
                d1.removeLast();

            // only push the elements that may contribute to minimum
            while (!d2.isEmpty() && arr[d2.peekLast()] >= arr[i])
                d2.removeLast();

            // add the current element's index
            d1.addLast(i);
            d2.addLast(i);

            // sum of min and max for current subarray
            sum += arr[d2.peekFirst()] + arr[d1.peekFirst()];
        }

        // return total sum
        return sum;
    }

    public static void main(String[] args) {
        // Example 1
        int arr1[] = new int[]{5, 9, 8, 3, -4, 2, 1, -5};
        int k1 = 4;
        System.out.println(sumOfMinMax(arr1, k1));

        // Example 2
        int arr2[] = new int[]{1, -1, 2, -2, 3, -3};
        int k2 = 2;
        System.out.println(sumOfMinMax(arr2, k2));
    }
}
17
2

C ++ ၏ subarrays အားလုံး၏အနိမ့်ဆုံးနှင့်အများဆုံး element မ်ား၏စုစုပေါင်းကိုရှာဖွေရန်ကုဒ် k

#include<bits/stdc++.h> 
using namespace std; 

int sumOfMinMax(int *arr, int k, int n) {
    // initialize sum as 0
    int sum = 0;
    
    // create 2 deques d1 and d2
    deque<int> d1;
    deque<int> d2;
    
    // first subarray
    for (int i = 0; i < k; i++) {
        // only push the elements that may contribute to maximum
        while (!d1.empty() && arr[d1.back()] <= arr[i]) {
            d1.pop_back();
        }
        
        // only push the elements that may contribute to minimum
        while (!d2.empty() && arr[d2.back()] >= arr[i]) {
            d2.pop_back();
        }
        
        // add the current element's index
        d1.push_back(i);
        d2.push_back(i);
    }
    
    // sum of min and max for first subarray
    sum += (arr[d2.front()] + arr[d1.front()]);
    
    // traverse the remaining subarray
    for (int i = k; i < n; i++) {
        // remove the previous element (sliding window technique)
        while (!d1.empty() && d1.front() <= (i -k)) {
            d1.pop_front();
        }
        while (!d2.empty() && d2.front() <= (i - k)) {
            d2.pop_front();
        }
        
        // only push the elements that may contribute to maximum
        while (!d1.empty() && arr[d1.back()] <= arr[i]) {
            d1.pop_back();
        }
        
        // only push the elements that may contribute to minimum
        while (!d2.empty() && arr[d2.back()] >= arr[i]) {
            d2.pop_back();
        }
        
        // add the current element's index
        d1.push_back(i);
        d2.push_back(i);
        
        // sum of min and max for current subarray
        sum += (arr[d1.front()] + arr[d2.front()]);
    }
    
    // return total sum
    return sum;
}

int main() {
    // Example 1
    int arr1[] = {5, 9, 8, 3, -4, 2, 1, -5};
    int k1 = 4;
    cout<<sumOfMinMax(arr1, k1, sizeof(arr1) / sizeof(arr1[0]))<<endl;

    // Example 2
    int arr2[] = {1, -1, 2, -2, 3, -3};
    int k2 = 2;
    cout<<sumOfMinMax(arr2, k2, sizeof(arr2) / sizeof(arr2[0]))<<endl;
    
    return 0;
}
17
2

ရှုပ်ထွေးဆန်းစစ်ခြင်း

အချိန်ရှုပ်ထွေး = အို (ဎ)
အာကာသရှုပ်ထွေး = အို (ဎ)
ဘယ်မှာ n ကပေးထားတဲ့ခင်းကျင်းထဲမှာစုစုပေါင်းဒြပ်စင်အရေအတွက်ဖြစ်ပါတယ်။

နံပါတ်များကိုကိုယ်စားပြုသော Queue များကိုကျွန်ုပ်တို့အသုံးပြုသည်။ အစဉ်လိုက်အစဉ်လိုက်တိုးလာသည်။ ထို့ကြောင့် algorithm သည် linear အချိန်ကိုရရှိသောကြောင့်လိုအပ်သောနေရာသည် linear ဖြစ်သည်။