جمع حداقل و حداکثر عناصر تمام زیرشاخه های اندازه k  


سطح دشواری سخت
اغلب در ByteDance یکی از سرمایه کوپن دونیا پایگاه داده گوگل Twilio Yandex
صف صف پنجره کشویی

بیان مسأله  

مسئله "مجموع عناصر حداقل و حداکثر تمام زیرآرایه های اندازه k" بیان می کند که به شما آرایه ای حاوی عددهای صحیح مثبت و منفی داده می شود ، جمع عناصر حداقل و حداکثر تمام زیر آرایه های اندازه k را پیدا کنید.

مثال ها  

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

توضیح
تمام زیر آرایه های اندازه 4 ،
{5 ، 9 ، 8 ، 3}: حداقل + حداکثر = 9 + 3 = 12
{9 ، 8 ، 3 ، -4}: دقیقه + حداکثر = -4 + 9 = 5
{8 ، 3 ، -4 ، 2}: دقیقه + حداکثر = -4 + 8 = 4
{3 ، -4 ، 2 ، 1}: دقیقه + حداکثر = -4 + 3 = -1
{-4 ، 2 ، 1 ، -5}: دقیقه + حداکثر = -5 + 2 = -3

جمع حداقل و حداکثر عناصر تمام زیرشاخه های اندازه kسنجاق

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

توضیح
تمام زیر آرایه های اندازه 2 ،
{1 ، -1}: حداقل + حداکثر = -1 + 1 = 0
{-1 ، 2}: حداقل + حداکثر = -1 + 2 = 1
{2 ، -2}: حداقل + حداکثر = -2 + 2 = 0
{-2 ، 3}: حداقل + حداکثر = -2 + 3 = 1
{3 ، -3}: حداقل + حداکثر = -3 + 3 = 0

روش  

رویکرد ساده لوحانه

تمام زیر آرایه های اندازه k را رد کنید تا حداقل و حداکثر عناصر آنها را پیدا کنید و مجموع را چاپ کنید.

  1. مقدار متغیر را مقدار 0 قرار دهید.
  2. یک حلقه برای i برابر است با 0 تا (n - k) ، جایی که n تعداد کل عناصر موجود در آن است صف. هر i به عنوان نقطه شروع یک آرایه فرعی با اندازه k عمل می کند.
  3. یک حلقه تو در تو برای j = i تا (i + k) اجرا کنید (شامل نمی شود) ، این حلقه یک زیر آرایه به اندازه k را نشان می دهد. این زیر آرایه را رد کنید و حداقل و حداکثر عناصر را پیدا کنید ، بگذارید اینها به ترتیب حداقل و حداکثر باشند.
  4. (حداقل + حداکثر) را به جمع اضافه کنید.
  5. در پایان پیمایش ، جمع کنید.
همچنین مشاهده کنید
صف اولویت در ++ C

که n تعداد کل عناصر در آرایه داده شده است.

جاوا کد برای یافتن جمع حداقل و حداکثر عناصر تمام زیرشاخه های اندازه 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 ++ کد برای یافتن مجموع حداقل و حداکثر عناصر تمام زیرشاخه های اندازه 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

تحلیل پیچیدگی

پیچیدگی زمان = O (n * k)
پیچیدگی فضا = O (1)

همچنین مشاهده کنید
Stack و Queue را با استفاده از Deque پیاده سازی کنید

در اینجا پیچیدگی زمان چند جمله ای است زیرا ما مسئله را برای هر زیر آرایه به طور مستقل حل می کنیم. از آنجا که ما فقط مقدار متغیر را ذخیره کرده ایم ؛ حداکثر و حداقل ، فضای مورد نیاز ثابت است.

رویکرد بهینه

ایجاد دو دیک d1 و d2 ، هر دو deque شاخص های عناصری را که ممکن است در حداقل و حداکثر یک زیر آرایه کمک کنند ذخیره می کنند. deque d1 شامل عناصر با نظم کاهش یافته از جلو به عقب و d2 شامل عناصر با افزایش ترتیب از جلو به عقب است.

  1. مقدار متغیر را به صورت 0 مقداردهی اولیه کنید. دو دیکشن d1 و d2 ایجاد کنید. اولین آرایه فرعی اندازه k را در نظر بگیرید.
  2. در حالی که عنصر فعلی زیر آرایه اندازه k بزرگتر یا برابر با عنصر در نمای عقب d1 است ، عنصر عقب Deque d1 را حذف کنید.
  3. در حالی که عنصر فعلی زیر آرایه اندازه k کوچکتر یا مساوی با عنصر در نمای عقب d2 است ، عنصر عقب Deque d2 را حذف کنید.
  4. شاخص فعلی را به عقب هر دو دیک اضافه کنید.
  5. عقب deque d1 شاخص حداکثر عنصر زیر آرایه و قسمت عقب deque d2 شاخص حداقل عنصر زیر آرایه است. مجموع عنصر حداکثر و حداقل را به متغیر sum اضافه کنید.
  6. زیر آرایه های فرعی k اندازه را رد کنید و مراحل 2 تا 5 را تکرار کنید. برای تمام زیر آرایه های باقی مانده از تکنیک پنجره کشویی و فقط عنصری را که در آرایه فرعی قبلی وجود ندارد پردازش کنید.
  7. پس از عبور از تمام آرایه های فرعی ، مبلغ را برگردانید.

کد جاوا برای یافتن جمع حداقل و حداکثر عناصر تمام زیرشاخه های اندازه 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 ++ کد برای یافتن مجموع حداقل و حداکثر عناصر تمام زیرشاخه های اندازه 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

تحلیل پیچیدگی

پیچیدگی زمان = O (N)
پیچیدگی فضا = O (N)
که n تعداد کل عناصر در آرایه داده شده است.

همچنین مشاهده کنید
تغییر صف

همانطور که از صف هایی استفاده کرده ایم که اعداد را به ترتیب کم و زیاد نشان می دهند ، بنابراین آنها یک بار عناصر را ذخیره می کنند. بنابراین الگوریتم به صورت خطی زمان می برد و بنابراین فضای مورد نیاز نیز خطی است.