Задача: 1802. Maximum Value at a Given Index in a Bounded Array
Сложность: medium

Даны три положительных целых числа: n, index и maxSum. Вам нужно построить массив nums (индексация с нуля), который удовлетворяет следующим условиям:

- nums.length == n
- nums[i] является положительным целым числом, где 0 <= i < n.
- abs(nums[i] - nums[i+1]) <= 1, где 0 <= i < n-1.
- Сумма всех элементов массива nums не превышает maxSum.
- nums[index] максимально возможен.

Верните значение nums[index] в построенном массиве.

Обратите внимание, что abs(x) равно x, если x >= 0, и -x в противном случае.

Пример:

Input: n = 4, index = 2,  maxSum = 6
Output: 2

👨‍💻 Алгоритм:

1⃣Определите функцию getSum(index, value) для вычисления минимальной суммы массива при условии, что nums[index] = value.

2⃣Инициализируйте диапазон поиска [left, right] значениями left = 1 и right = maxSum. Выполните бинарный поиск: вычислите mid = (left + right + 1) / 2 и проверьте, если getSum(index, mid) <= maxSum. Если условие выполняется, установите left = mid, иначе установите right = mid - 1.

3⃣Верните left по завершении бинарного поиска.

😎 Решение:

class Solution {
    private func getSum(_ index: Int, _ value: Int, _ n: Int) -> Int64 {
        var count: Int64 = 0
        if value > index {
            count += Int64(value + value - index) * Int64(index + 1) / 2
        } else {
            count += Int64(value + 1) * Int64(value) / 2 + Int64(index - value + 1)
        }
        if value >= n - index {
            count += Int64(value + value - n + 1 + index) * Int64(n - index) / 2
        } else {
            count += Int64(value + 1) * Int64(value) / 2 + Int64(n - index - value)
        }
        return count - Int64(value)
    }

    func maxValue(_ n: Int, _ index: Int, _ maxSum: Int) -> Int {
        var left = 1, right = maxSum
        while left < right {
            let mid = (left + right + 1) / 2
            if getSum(index, mid, n) <= maxSum {
                left = mid
            } else {
                right = mid - 1
            }
        }
        return left
    }
}

Ставь 👍 и забирай 📚 Базу знаний