Минимизируйте максимальную разницу между высотами

Приведенные выше коды работают, однако я не нашел много объяснений, поэтому я попытаюсь добавить некоторые из них, чтобы помочь развить интуицию.

Для любой башни, если вы решите увеличить ее высоту с H_i до H_i + K, то вы также можете увеличить высоту всех более коротких башен, так как это не повлияет на максимум. Точно так же, если вы решите уменьшить высоту башни с H_i до H_i − K, то вы также можете уменьшить высоту всех более высоких башен.
Мы воспользуемся этим, у нас есть n зданий, и мы постараемся сделать каждое из них самым высоким и посмотрим, какое из зданий будет самым высоким, что даст нам наименьший диапазон высот (это наш ответ).
Поясню:

Итак, что мы хотим сделать, это -
1) Сначала мы сортируем массив (вы скоро поймете, почему).

2) Затем для каждого здания от i = 0 до n-2^{[ 1]}, мы пытаемся сделать его самым высоким (добавляя K к зданию, добавляя K к зданиям слева от него и вычитая K из зданий справа).

Допустим, мы строим H_i, мы добавили к нему букву K и здания до него и вычел K из зданий после него.

Таким образом, минимальная высота зданий теперь будет min(H_{0 + K, Hi+1 – K),
т.е. мин(1-е здание + K, следующее здание справа - K)}.

(Примечание: это потому, что мы отсортировали массив. Убедитесь сами, взяв несколько примеров.)

Аналогично, максимальная высота зданий будет max( H_i + K, H_n-1 – K),
т. е. max(текущее здание + K, последнее здание справа - K).

3) max - min дает вам диапазон.

^[1]Обратите внимание, что когда i = n-1. В этом случае после текущего здания нет здания, поэтому мы добавляем K к каждому зданию, поэтому диапазон будет просто height[n-1] - height[0], так как K добавляется ко всему, поэтому он отменяет вне.

Вот реализация Java, основанная на приведенной выше идее:

class Solution {
    int getMinDiff(int[] arr, int n, int k) {
        Arrays.sort(arr);
        int ans = arr[n-1] - arr[0];
        int smallest = arr[0] + k, largest = arr[n-1]-k;
        for(int i = 0; i < n-1; i++){
            int min = Math.min(smallest, arr[i+1]-k);
            int max = Math.max(largest, arr[i]+k);
            if(min < 0) 
                continue;
            ans = Math.min(ans, max-min);
        }
        return ans;
    }
}

Этот код Python может вам помочь. Код говорит сам за себя.

def getMinDiff(arr, n, k):
    arr = sorted(arr)
    ans = arr[-1]-arr[0] #this case occurs when either we subtract k or add k to all elements of the array
    for i in range(n):
        mn=min(arr[0]+k, arr[i]-k) #after sorting, arr[0] is minimum. so adding k pushes it towards maximum. We subtract k from arr[i] to get any other worse (smaller) minimum. worse means increasing the diff b/w mn and mx
        mx=max(arr[n-1]-k, arr[i]+k) # after sorting, arr[n-1] is maximum. so subtracting k pushes it towards minimum. We add k to arr[i] to get any other worse (bigger) maximum. worse means increasing the diff b/w mn and mx
        ans = min(ans, mx-mn)
    return ans

int getMinDiff(int a[], int n, int k) {
        sort(a,a+n); 
        int i,mx,mn,ans;
        ans = a[n-1]-a[0];  // this can be one possible solution
        
        for(i=0;i<n;i++)
        {
            if(a[i]>=k)  // since height of tower can't be -ve so taking only +ve heights
            {
                mn = min(a[0]+k, a[i]-k);
                mx = max(a[n-1]-k, a[i-1]+k);
                ans = min(ans, mx-mn);
            }
        }
        return ans;
    }

Это код C++, он прошел все тесты.

Вот решение: -

Но прежде чем перейти к решению, вот некоторая информация, необходимая для его понимания. В лучшем случае минимальная разница будет равна нулю. Это может произойти только в двух случаях: (1) массив содержит дубликаты или (2) для элемента, скажем, «x», в массиве существует другой элемент со значением «x + 2*k».

Идея довольно проста.

1. Сначала мы отсортировали массив.
2. Далее мы попытаемся найти либо оптимальное значение (для которого ответ будет равен нулю), либо, по крайней мере, ближайшее число к оптимальному значению, используя >Двоичный поиск

Вот реализация алгоритма Javascript: -

function minDiffTower(arr, k) {
    arr = arr.sort((a,b) => a-b);
    let minDiff = Infinity;
    let prev = null;

    for (let i=0; i<arr.length; i++) {
        let el = arr[i];
        
        // Handling case when the array have duplicates
        if (el == prev) {
            minDiff = 0;
            break;
        }
        prev = el;

        let targetNum = el + 2*k; // Lets say we have an element 10. The difference would be zero when there exists an element with value 10+2*k (this is the 'optimum value' as discussed in the explaination
        let closestMatchDiff =  Infinity; // It's not necessary that there would exist 'targetNum' in the array, so we try to find the closest to this number using Binary Search
        let lb = i+1;
        let ub = arr.length-1;
        while (lb<=ub) {
            let mid = lb + ((ub-lb)>>1);
            let currMidDiff =  arr[mid] > targetNum ? arr[mid] - targetNum : targetNum - arr[mid];
            closestMatchDiff = Math.min(closestMatchDiff, currMidDiff); 
            if (arr[mid] == targetNum) break; // in this case the answer would be simply zero, no need to proceed further
            else if (arr[mid] < targetNum) lb = mid+1;
            else ub = mid-1;
        }
        minDiff = Math.min(minDiff, closestMatchDiff);
    }
    return minDiff;
}

Вот код C++, я продолжил с того места, где вы остановились. Код говорит сам за себя.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int minDiff(int arr[], int n, int k)
{
    // If the array has only one element.
    if (n == 1)
    {
        return 0;
    }
    //sort all elements
    sort(arr, arr + n);

    //initialise result
    int ans = arr[n - 1] - arr[0];

    //Handle corner elements
    int small = arr[0] + k;
    int big = arr[n - 1] - k;
    if (small > big)
    {
        // Swap the elements to keep the array sorted.
        int temp = small;
        small = big;
        big = temp;
    }

    //traverse middle elements
    for (int i = 0; i < n - 1; i++)
    {
        int subtract = arr[i] - k;
        int add = arr[i] + k;

        // If both subtraction and addition do not change the diff.
        // Subtraction does not give new minimum.
        // Addition does not give new maximum.
        if (subtract >= small or add <= big)
        {
            continue;
        }

        // Either subtraction causes a smaller number or addition causes a greater number.
        //Update small or big using greedy approach.
        // if big-subtract causes smaller diff, update small Else update big
        if (big - subtract <= add - small)
        {
            small = subtract;
        }
        else
        {
            big = add;
        }
    }
    return min(ans, big - small);
}

int main(void)
{
    int arr[] = {1, 5, 15, 10};
    int n = sizeof(arr) / sizeof(arr[0]);
    int k = 3;
    cout << "\nMaximum difference is: " << minDiff(arr, n, k) << endl;
    return 0;
}