Άθροισμα ελάχιστων και μέγιστων στοιχείων όλων των υποπεριοχών μεγέθους k


Επίπεδο δυσκολίας Σκληρά
Συχνές ερωτήσεις ByteDance Capital One Κουπόνι Ντούνια Βάσεις δεδομένων 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}: 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

Άθροισμα ελάχιστων και μέγιστων στοιχείων όλων των υποπεριοχών μεγέθους 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

Προσέγγιση

Naive προσέγγιση

Περάστε όλες τις υπο-σειρές μεγέθους k για να βρείτε τα ελάχιστα και μέγιστα στοιχεία τους και εκτυπώστε το άθροισμα.

  1. Αρχικοποιήστε ένα μεταβλητό άθροισμα ως 0.
  2. Εκτελέστε έναν βρόχο για i είναι 0 έως (n - k), όπου n είναι ο συνολικός αριθμός στοιχείων στο δεδομένο παράταξη. Κάθε εγώ ενεργεί ως σημείο εκκίνησης μιας υπο-συστοιχίας μεγέθους k.
  3. Εκτελέστε έναν ένθετο βρόχο για j = i έως (i + k) (δεν περιλαμβάνεται), αυτός ο βρόχος αντιπροσωπεύει μια υπο-σειρά μεγέθους k. Διασχίστε αυτήν την υπο-συστοιχία και βρείτε τα ελάχιστα και μέγιστα στοιχεία, αφήστε αυτά να είναι ελάχιστα και μέγιστα αντίστοιχα.
  4. Προσθέστε (min + max) στο άθροισμα.
  5. Στο τέλος της διασταύρωσης, επιστρέψτε το άθροισμα.

όπου n είναι ο συνολικός αριθμός στοιχείων στο δεδομένο πίνακα.

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 ++ Κωδικός για εύρεση Αθροίσματος ελάχιστων και μέγιστων στοιχείων όλων των υποζώνων μεγέθους 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)
Διαστημική πολυπλοκότητα = Ο (1)

Εδώ η πολυπλοκότητα του χρόνου είναι πολυώνυμη, διότι επιλύουμε το πρόβλημα για κάθε υπο-πίνακα ανεξάρτητα. Δεδομένου ότι έχουμε αποθηκεύσει μόνο: y δύο μεταβλητές για μέγιστο και ελάχιστο, ο απαιτούμενος χώρος είναι σταθερός.

Βέλτιστη προσέγγιση

Δημιουργήστε δύο Ντεκ d1 και d2, και οι δύο δίσκοι αποθηκεύουν τους δείκτες στοιχείων που μπορούν να συνεισφέρουν στο ελάχιστο και το μέγιστο μιας υπο-συστοιχίας. Το Deque d1 περιέχει τα στοιχεία σε φθίνουσα σειρά από εμπρός σε πίσω και το d2 περιέχει στοιχεία σε αυξανόμενη σειρά από εμπρός σε πίσω.

  1. Αρχικοποιήστε ένα μεταβλητό άθροισμα ως 0. Δημιουργήστε δύο deques d1 και d2. Εξετάστε το πρώτο υποσύνολο μεγέθους k.
  2. Ενώ το τρέχον στοιχείο της υποδιάταξης μεγέθους k είναι μεγαλύτερο ή ίσο με το στοιχείο στο ευρετήριο πίσω του d1, αφαιρέστε το πίσω στοιχείο του Deque d1.
  3. Ενώ το τρέχον στοιχείο της υπο-συστοιχίας μεγέθους k είναι μικρότερο ή ίσο με το στοιχείο στο ευρετήριο πίσω του d2, αφαιρέστε το πίσω στοιχείο του Deque d2.
  4. Προσθέστε τον τρέχοντα δείκτη στο πίσω μέρος και των δύο δίσκων.
  5. Το πίσω μέρος του deque d1 είναι ο δείκτης του μέγιστου στοιχείου της υπο-συστοιχίας και το πίσω μέρος του deque d2 είναι ο δείκτης του ελάχιστου στοιχείου της υπο-συστοιχίας. Προσθέστε το άθροισμα του μέγιστου και του ελάχιστου στοιχείου στο μεταβλητό άθροισμα.
  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

Ανάλυση πολυπλοκότητας

Πολυπλοκότητα χρόνου = O (n)
Διαστημική πολυπλοκότητα = O (n)
όπου n είναι ο συνολικός αριθμός στοιχείων στο δεδομένο πίνακα.

Καθώς έχουμε χρησιμοποιήσει ουρές που αντιπροσωπεύουν τους αριθμούς σε φθίνουσα και αυξανόμενη σειρά, έτσι αποθηκεύουν τα στοιχεία μία φορά. Έτσι ο αλγόριθμος παίρνει γραμμικό χρόνο, και έτσι ο απαιτούμενος χώρος είναι επίσης γραμμικός.