Medium

题目描述

给你三个正整数：n、index 和 maxSum。你想要构造一个同时满足下述所有条件的数组 nums（下标从 0 开始计数）：

  • 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 的绝对值。

示例 1：

输入：n = 4, index = 2, maxSum = 6
输出：2
解释：数组 [1,2,2,1] 满足所有条件。
不存在其他满足所有条件且 nums[2] == 3 的数组，所以 2 是 nums[2] 的最大值。

示例 2：

输入：n = 6, index = 1, maxSum = 10
输出：3

约束条件：

  • 1 <= n <= maxSum <= 10^9
  • 0 <= index < n

解题思路

这道题要求构造一个有界数组，使得指定位置的值最大。关键观察是：为了最大化 nums[index]，我们应该让数组以该位置为峰值，向两边递减。

核心思路：

  1. 贪心策略：以 index 为中心构造一个"山峰"形数组，向左右两边递减，直到边界或者值为1
  2. 二分搜索：在可能的取值范围内二分查找最大的 nums[index]
  3. 数学计算：对于给定的峰值，快速计算整个数组的最小和

算法流程：

  • 二分搜索范围：[1, maxSum]
  • 对于每个候选值 mid，计算以它为峰值时数组的最小和
  • 如果和 ≤ maxSum，说明可行，尝试更大的值
  • 否则说明太大，减小搜索范围

关键计算： 对于峰值 val，左右两部分的最小和可以用等差数列求和公式快速计算。例如左边部分：

  • 如果 val > index + 1，和为 val + (val-1) + ... + (val-index)
  • 否则部分为递减序列，部分为1

时间复杂度为 O(log(maxSum))，空间复杂度为 O(1)。

代码实现

class Solution {
public:
    int maxValue(int n, int index, int maxSum) {
        auto getSum = [&](long long val) -> long long {
            long long sum = val;
            
            // 计算左边部分的和
            long long leftCount = index;
            if (val > leftCount) {
                sum += (val - 1 + val - leftCount) * leftCount / 2;
            } else {
                sum += (val - 1) * val / 2 + (leftCount - val + 1);
            }
            
            // 计算右边部分的和
            long long rightCount = n - index - 1;
            if (val > rightCount) {
                sum += (val - 1 + val - rightCount) * rightCount / 2;
            } else {
                sum += (val - 1) * val / 2 + (rightCount - val + 1);
            }
            
            return sum;
        };
        
        int left = 1, right = maxSum;
        int result = 1;
        
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (getSum(mid) <= maxSum) {
                result = mid;
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        
        return result;
    }
};

class Solution:
    def maxValue(self, n: int, index: int, maxSum: int) -> int:
        def getSum(val):
            total = val
            
            # 计算左边部分的和
            left_count = index
            if val > left_count:
                total += (val - 1 + val - left_count) * left_count // 2
            else:
                total += (val - 1) * val // 2 + (left_count - val + 1)
            
            # 计算右边部分的和
            right_count = n - index - 1
            if val > right_count:
                total += (val - 1 + val - right_count) * right_count // 2
            else:
                total += (val - 1) * val // 2 + (right_count - val + 1)
            
            return total
        
        left, right = 1, maxSum
        result = 1
        
        while left <= right:
            mid = (left + right) // 2
            if getSum(mid) <= maxSum:
                result = mid
                left = mid + 1
            else:
                right = mid - 1
        
        return result

public class Solution {
    public int MaxValue(int n, int index, int maxSum) {
        long GetSum(long val) {
            long sum = val;
            
            // 计算左边部分的和
            long leftCount = index;
            if (val > leftCount) {
                sum += (val - 1 + val - leftCount) * leftCount / 2;
            } else {
                sum += (val - 1) * val / 2 + (leftCount - val + 1);
            }
            
            // 计算右边部分的和
            long rightCount = n - index - 1;
            if (val > rightCount) {
                sum += (val - 1 + val - rightCount) * rightCount / 2;
            } else {
                sum += (val - 1) * val / 2 + (rightCount - val + 1);
            }
            
            return sum;
        }
        
        int left = 1, right = maxSum;
        int result = 1;
        
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (GetSum(mid) <= maxSum) {
                result = mid;
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        
        return result;
    }
}

var maxValue = function(n, index, maxSum) {
    const getSum = (val) => {
        let sum = val;
        
        // 计算左边部分的和
        let leftCount = index;
        if (val > leftCount) {
            sum += (val - 1 + val - leftCount) * leftCount / 2;
        } else {
            sum += (val - 1) * val / 2 + (leftCount - val + 1);
        }
        
        // 计算右边部分的和
        let rightCount = n - index - 1;
        if (val > rightCount) {
            sum += (val - 1 + val - rightCount) * rightCount / 2;
        } else {
            sum += (val - 1) * val / 2 + (rightCount - val + 1);
        }
        
        return sum;
    };
    
    let left = 1, right = maxSum;
    let result = 1;
    
    while (left <= right) {
        let mid = Math.floor((left + right) / 2);
        if (getSum(mid) <= maxSum) {
            result = mid;
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度大小
时间复杂度O(log(maxSum))
空间复杂度O(1)