크기가 k 인 모든 부분 배열의 최소 및 최대 요소의 합

난이도 하드
자주 묻는 질문 ByteDance 자본 하나 쿠폰 Dunia 데이터 브릭 구글 Twilio Yandex 주차
배열 슬라이딩 윈도우조회수 36

문제 정책

“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. 순회가 끝나면 합계를 반환합니다.

여기서 n은 주어진 배열의 총 요소 수입니다.

크기가 k 인 모든 하위 배열의 최소 및 최대 요소의 합계를 찾는 Java 코드

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 인 모든 하위 배열의 최소 및 최대 요소의 합계를 찾는 C ++ 코드

#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)

여기서 시간 복잡도는 각 하위 배열의 문제를 독립적으로 해결하기 때문에 다항식입니다. 최대 및 최소에 대한 두 개의 변수 만 저장했기 때문에 필요한 공간은 일정합니다.

최적의 접근 방식

두 개 만들기 데케 d1 및 d2, 두 deques 모두 하위 배열의 최소 및 최대에 기여할 수있는 요소의 인덱스를 저장합니다. Deque d1은 앞쪽에서 뒤쪽으로 내림차순으로 요소를 포함하고 d2는 앞쪽에서 뒤쪽으로 오름차순으로 요소를 포함합니다.

  1. 변수 합계를 0으로 초기화합니다. 두 개의 deques d1과 d2를 만듭니다. 크기 k의 첫 번째 하위 배열을 고려하십시오.
  2. 크기가 k 인 하위 배열의 현재 요소가 d1의 인덱스 뒷면에있는 요소보다 크거나 같지만 Deque d1의 뒷면 요소를 제거합니다.
  3. 크기가 k 인 하위 배열의 현재 요소가 d2의 인덱스 후면에있는 요소보다 작거나 같지만 Deque d2의 후면 요소를 제거합니다.
  4. 두 deques 뒤에 현재 색인을 추가합니다.
  5. deque d1의 후면은 서브 어레이의 최대 요소 인덱스이고 deque d2의 후면은 서브 어레이의 최소 요소 인덱스입니다. 최대 및 최소 요소의 합계를 변수 합계에 더합니다.
  6. 크기 k의 나머지 하위 배열을 횡단하고 2 ~ 5 단계를 반복합니다. 나머지 모든 하위 배열에 대해 슬라이딩 윈도우 기술 이전 하위 배열에없는 요소 만 처리합니다.
  7. 모든 하위 배열을 탐색 한 후 합계를 반환합니다.

크기가 k 인 모든 하위 배열의 최소 및 최대 요소의 합계를 찾는 Java 코드

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 인 모든 하위 배열의 최소 및 최대 요소의 합계를 찾는 C ++ 코드

#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은 주어진 배열의 총 요소 수입니다.

감소 및 증가 순서로 숫자를 나타내는 큐를 사용 했으므로 요소를 한 번 저장합니다. 따라서 알고리즘은 선형 시간이 걸리므로 필요한 공간도 선형입니다.

Translate »