K չափի բոլոր ենթածրագրերի նվազագույն և առավելագույն տարրերի հանրագումարը


Դժվարության մակարդակ Դժվար
Հաճախակի հարցնում են ByteDance Capital One CouponDunia Տվյալների շտեմարաններ Google 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. Run- ի համար մի օղակ հավասար է 0-ից (n - k), որտեղ n- ը տրված տարրերի ընդհանուր թիվն է դասավորություն, Յուրաքանչյուր i հանդես է գալիս որպես k չափի ենթախմբի ելակետ:
  3. Գործարկել տեղադրված օղակ j = i- ից (i + k) (ներառված չէ) համար, այս օղակը ներկայացնում է k չափի ենթադաս: Անցեք այս ենթաշղթան և գտեք նվազագույն և առավելագույն տարրերը, թող դրանք համապատասխանաբար լինեն min և max:
  4. Գումարին ավելացնել (րոպե + առավելագույն):
  5. Անցման վերջում վերադարձեք գումարը:

որտեղ 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

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

Բարդության վերլուծություն

Timeամանակի բարդություն = O (n * k)
Տիեզերական բարդություն = Ո (1)

Այստեղ ժամանակի բարդությունը բազմանդամ է, քանի որ յուրաքանչյուր ենթախմբի համար խնդիրը լուծվում է ինքնուրույն: Քանի որ մենք պահպանում ենք միայն. Y երկու փոփոխական առավելագույնի և նվազագույնի համար, պահանջվող տարածքը հաստատուն է:

Օպտիմալ մոտեցում

Ստեղծեք երկուս Դիկե d1 և d2, այնպես էլ deque- ն պահպանում է այն տարրերի ցուցիչները, որոնք կարող են նպաստել ենթախմբի նվազագույն և առավելագույնի: Deque d1- ն պարունակում է տարրերը նվազող կարգով `առջևից հետև, և d2 պարունակում է տարրեր` առջևից հետևի ուղղությամբ աճող կարգով:

  1. Նախապատկերացնել փոփոխական գումարը որպես 0. Ստեղծել երկու deque d1 և d2: Դիտարկենք k չափի առաջին ենթա-զանգվածը:
  2. Չնայած k չափի ենթախմբի ներկայիս տարրը ավելի մեծ է կամ հավասար է d1- ի ցուցիչի թիկունքում գտնվող տարրին, հեռացրեք Deque d1- ի հետևի տարրը:
  3. Չնայած k չափի ենթախմբի ներկայիս տարրը փոքր է կամ հավասար է d2- ի ցուցիչի հետին մասում գտնվող տարրին, հեռացրեք Deque d2- ի հետևի տարրը:
  4. Ընթացիկ ցուցիչը ավելացրեք երկու դեկերի հետևում:
  5. Deque de1 d2- ը ենթախաղի առավելագույն տարրի ինդեքսն է, իսկ deque dXNUMX deque- ը ՝ ենթախմբի նվազագույն տարրի ինդեքսը: Փոփոխական գումարին ավելացրու առավելագույն և նվազագույն տարրի գումարը:
  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

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

Բարդության վերլուծություն

Timeամանակի բարդություն = O (n)
Տիեզերական բարդություն = O (n)
որտեղ n տրված զանգվածում տարրերի ընդհանուր թիվն է:

Քանի որ մենք օգտագործել ենք հերթեր, որոնք թվերը ներկայացնում են նվազող և աճող կարգով, այնպես որ դրանք պահում են տարրերը մեկ անգամ: Այսպիսով ալգորիթմը տևում է գծային ժամանակ, և այդպիսով պահանջվող տարածքը նույնպես գծային է: