Сума мінімальних та максимальних елементів усіх підмасивів розміром k  


Рівень складності Жорсткий
Часто запитують у ByteDance Capital One КупонДунія Збір даних Google Twilio Яндекс
масив Чергу Розсувне вікно

Постановка проблеми  

Задача “Сума мінімальних та максимальних елементів усіх підмасивів розміром 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}: min + max = -4 + 8 = 4
{3, -4, 2, 1}: min + max = -4 + 3 = -1
{-4, 2, 1, -5}: хв + макс = -5 + 2 = -3

Сума мінімальних та максимальних елементів усіх підмасивів розміром kPin

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. Обходьте цей підмасив і знайдіть мінімальний та максимальний елементи, нехай вони будуть min та max відповідно.
  4. Додайте (min + max) до суми.
  5. В кінці обходу поверніть суму.
Дивись також
Черга пріоритетів у C ++

де n - загальна кількість елементів у даному масиві.

Код Java для пошуку суми мінімальних та максимальних елементів усіх підмасивів розміром 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

Код С ++ для пошуку суми мінімальних та максимальних елементів усіх підмасивів розміром 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)

Дивись також
Впровадити стек і чергу за допомогою Deque

Тут складність часу поліноміальна, оскільки ми вирішуємо задачу для кожного підмасиву самостійно. Оскільки ми зберігаємо лише; y дві змінні для максимуму та мінімуму, необхідний простір є постійним.

Оптимальний підхід

Створіть два Deque d1 і d2, обидва модулі зберігають індекси елементів, які можуть сприяти мінімуму та максимуму підмасиву. 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. Після обходу всіх підмасивів поверніть суму.

Код 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

Код С ++ для пошуку суми мінімальних та максимальних елементів усіх підмасивів розміром 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 - загальна кількість елементів у даному масиві.

Дивись також
Реверсування черги

Оскільки ми використовували черги, що представляють числа в порядку зменшення та збільшення, так вони зберігають елементи один раз. Таким чином, алгоритм займає лінійний час, а отже, необхідний простір також є лінійним.