難度：★★★☆☆
類型：數(shù)組
方法：數(shù)學(xué)

題目

力扣鏈接請移步本題傳送門
更多力扣中等題的解決方案請移步力扣中等題目錄

給你三個正整數(shù) n、index 和 maxSum 。你需要構(gòu)造一個同時滿足下述所有條件的數(shù)組 nums（下標(biāo) 從 0 開始 計數(shù)）：

nums.length == n
nums[i] 是 正整數(shù) ，其中 0 <= i < n
abs(nums[i] - nums[i+1]) <= 1 ，其中 0 <= i < n-1
nums 中所有元素之和不超過 maxSum
nums[index] 的值被 最大化
返回你所構(gòu)造的數(shù)組中的 nums[index] 。

注意：abs(x) 等于 x 的前提是 x >= 0 ；否則，abs(x) 等于 -x 。

示例 1：

輸入：n = 4, index = 2, maxSum = 6
輸出：2
解釋：數(shù)組 [1,1,2,1] 和 [1,2,2,1] 滿足所有條件。不存在其他在指定下標(biāo)處具有更大值的有效數(shù)組。

示例 2：

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

提示：

1 <= n <= maxSum <= 109
0 <= index < n

解答

方案1：二分法

題目的要求是，希望我們在構(gòu)建長度為n的數(shù)組時盡可能最大化index位置處的元素，并且限制了數(shù)組元素和maxSum以及相鄰元素的最大梯度為1。

很容易發(fā)現(xiàn)，為了滿足maxSum條件下最大化index位置處元素，我們應(yīng)該讓數(shù)組在index位置處盡可能尖銳，而梯度的限制決定了該位置處的值會影響相鄰位置處的值，進而影響整個數(shù)組的排布。如果把數(shù)組各個位置畫一條折線圖，就會發(fā)現(xiàn)我們希望的結(jié)果是呈現(xiàn)一個倒直角三角形的形態(tài)。

我們定義一個函數(shù)f，函數(shù)的自變量x代表了index處的數(shù)值，函數(shù)的返回值代表了在index是x的情況下，整個數(shù)組的和。很容易發(fā)現(xiàn)，f(x)隨著x的增加是單調(diào)遞增的，題目實際上是給出了一個因變量的范圍，讓我們求取最大的x，對于這一類單調(diào)函數(shù)求自變量的問題，常?？梢允褂枚址ń鉀Q。

定義一個函數(shù)check，函數(shù)的輸入為x，函數(shù)的輸出為布爾量，代表index位置處填寫x，并且滿足梯度約束的情況下，對應(yīng)的數(shù)組和f(x)能否滿足最大和maxSum的限制。其實f(x)是一個分段函數(shù)，根據(jù)index左側(cè)元素的個數(shù)left和右側(cè)元素的個數(shù)right，可以計算兩者當(dāng)中的最小值x1與最大值x2，函數(shù)在x1和x2兩個分界點處分段。根據(jù)輸入x與x1和x2之間的數(shù)值關(guān)系可以判斷函數(shù)應(yīng)該屬于哪一段，進而使用該段內(nèi)的函數(shù)表達式，每一段的函數(shù)表達式常常會用到等差數(shù)列求和公式得到，詳細公式不再贅述。

有了判別函數(shù)check，就可以使用二分法，二分法搜索的上下界可以設(shè)定為0和maxSum，使用通用二分搜索代碼即可實現(xiàn)。這里需要注意一下最終結(jié)果的處理。

class Solution:
    def maxValue(self, n: int, index: int, maxSum: int) -> int:

        left, right = index, n - 1 - index
        x1, x2 = min(left, right), max(left, right)

        def check(x):
            if x <= x1:
                s = (x - 1) ** 2 + n
            elif x <= x2:
                s = x + (((x - 1) + (x - x1)) * x1) // 2 + (((x - 1) + 1) * (x - 1)) // 2 + (x2 - (x - 1))
            else:
                s = x + (((x - 1) + (x - x1)) * x1) // 2 + (((x - 1) + (x - x2)) * x2) // 2
            return s <= maxSum

        left, right = 1, maxSum

        while left < right:
            mid = left + (right - left) // 2
            if check(mid):
                left = mid + 1
            else:
                right = mid

        return left if check(left) else left - 1


s = Solution()
print(s.maxValue(1, 0, 24))
print(s.maxValue(3, 2, 18))
print(s.maxValue(4, 0, 4))
print(s.maxValue(4, 2, 6))
print(s.maxValue(6, 1, 10))

方案2：數(shù)學(xué)

由于上述分段函數(shù)的公式我們可以嚴格得知，因此求出其反函數(shù)，即可通過反函數(shù)得到自變量的取值。

為了便于讀者理解，我們將題目稍作修改，最小值設(shè)置為零而不是1，這里舉個例子，設(shè)n=11，index=7的情況。那么對于不同x，增量increment和當(dāng)前和f(x)會是這樣：

"""
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
left = 7, right = 3, x1 = 3, x2 = 7

x                array              increment   f(x)
0   [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]   0       0
1   [0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0]   1       1
2   [0, 0, 0, 0, 0, 0, 1, 2, 1, 0, 0]   3       1 + 3 = 4
3   [0, 0, 0, 0, 0, 1, 2, 3, 2, 1, 0]   5       1 + 3 + 5 = 9

4   [0, 0, 0, 0, 1, 2, 3, 4, 3, 2, 1]   7       9 + 7 = 16
5   [0, 0, 0, 1, 2, 3, 4, 5, 4, 3, 2]   8       9 + 7 + 8 = 24
6   [0, 0, 1, 2, 3, 4, 5, 6, 5, 4, 3]   9       9 + 7 + 8 + 9 = 33
7   [0, 1, 2, 3, 4, 5, 6, 7, 6, 5, 4]   10      9 + 7 + 8 + 9 + 10 = 43

8   [1, 2, 3, 4, 5, 6, 7, 8, 7, 6, 5]   11      43 + 11 = 54
9   [2, 3, 4, 5, 6, 7, 8, 9, 8, 7, 6]   11      43 + 11 + 11 = 65
...
"""

我們看到，在不同的分段內(nèi)，增量是逐漸減小的，且變化的數(shù)值在三段內(nèi)分別是2,1和0。設(shè)x1和x2處的函數(shù)值分別是f1和f2，原函數(shù)的表達式為：

根據(jù)數(shù)學(xué)的原理，我們可以計算得到這個分段函數(shù)的反函數(shù)：

在求解反函數(shù)時，中間這一段比較復(fù)雜，涉及到一元二次方程的求解公式。不過不管是一元二次方程還是等差數(shù)列求和公式，都是高中的知識，這里不再贅述。

有了上面的數(shù)學(xué)法寶，我們就可以在O(1)的時間復(fù)雜度和O(1)的空間復(fù)雜度內(nèi)快速得到結(jié)果。

class Solution:
    def maxValue(self, n: int, index: int, maxSum: int) -> int:

        left, right = index, n - 1 - index
        x1, x2 = min(left, right), max(left, right)

        f1 = x1 ** 2
        f2 = f1 + ((2 * x1 + 1) + (2 * x1 + (x2 - x1))) * (x2 - x1) // 2

        if maxSum <= f1:
            return int(maxSum ** 0.5)
        if maxSum <= f2:
            return int((- (4 * x1 + 1) + ((4 * x1 + 1) ** 2 + 8 * (maxSum - f1)) ** 0.5) / 2) + x1
        return int((maxSum - f2) / n) + x2

這里還需要注意的是，我們的函數(shù)允許數(shù)組中出現(xiàn)0，但是題目中要求數(shù)組中所有元素最少也是1，因此需要針對這個問題處理一下，不過處理過程非常簡單。

class Solution:
    def maxValue(self, n: int, index: int, maxSum: int) -> int:

        left, right = index, n - 1 - index
        x1, x2 = min(left, right), max(left, right)

        f1 = x1 ** 2
        f2 = f1 + ((2 * x1 + 1) + (2 * x1 + (x2 - x1))) * (x2 - x1) // 2

        maxSum -= n

        if maxSum <= f1:
            res = int(maxSum ** 0.5)
        elif maxSum <= f2:
            res = int((- (4 * x1 + 1) + ((4 * x1 + 1) ** 2 + 8 * (maxSum - f1)) ** 0.5) / 2) + x1
        else:
            res = int((maxSum - f2) / n) + x2
        return res + 1


s = Solution()
print(s.maxValue(4, 0, 4))
print(s.maxValue(4, 2, 6))
print(s.maxValue(6, 1, 10))

如有疑問或建議，歡迎評論區(qū)留言~

有關(guān)更多力扣中等題的python解決方案，請移步力扣中等題解析