[Leetcode] 1802. Maximum Value at a Given Index in a Bounded Array (Medium)

概述

題目

https://leetcode.com/problems/maximum-value-at-a-given-index-in-a-bounded-array/
題意為給定一 n 位置，第 index 位置必須是最大值，而後所有相鄰數差異要 <= 1 且 total sum 要小於等於 maxSum，求 index 值可以的最大

心得

屬於 Try and Verify 的題目，先猜一數字看是否符合，再依符合或不符合往更大或更小方向猜，以逼近正確結果；

Binary Search

思路

猜後驗證，逼近方式則以 Binary Search 方式處理

程式

class Solution(object):
    def maxValue(self, n, index, maxSum):
        """
        :type n: int
        :type index: int
        :type maxSum: int
        :rtype: int
        """
        l, r = 0, maxSum+1

        def test(m):
            smv = 0

            # 左邊 (含第 index 位)
            if m > index:
                smv += (m + m-index) * (index+1) // 2
            else:
                smv += index+1 - m
                smv += (1+m)*m//2
            
            # 右邊 (含第 index 位)
            if m > n-index:
                smv += (m-(n-index)+1+m) * (n-index) // 2
            else:
                smv += n - (index+m)
                smv += (1+m)*m//2

            # 重覆計算第 index 位需減去
            return smv - m <= maxSum

        while l<r:
            m = (l+r) // 2
            if test(m-1) and not test(m):
                return m-1
            if not test(m):
                r = m
            else:
                l = m+1
        return l-1

Complexity

Time Complexity: O( log(maxSum) )
Binary Search 由 0 至 maxSum+1，故為 log(maxSum)

Space Complexity: O(1)
基本上無使用到額外空間

Math

思路

from louis925，預處理將每個位置都先 -1，最後再 +1 回來，則可將題目想成由 index 位置切成的左右兩個圖形，可以是三角形或者是梯形，取決於 index 所在位置

程式

class Solution(object):
    def maxValue(self, n, index, maxSum):
        """
        :type n: int
        :type index: int
        :type maxSum: int
        :rtype: int
        """
        # 預處理將所有位置都 -1
        maxSum -= n

        # 因 index 位置具左右對稱性，故將其轉換為必靠右邊之位置
        if index < n // 2:
            index = n - index - 1

        # index 左右的位置個數
        n_lef = index
        n_rit = n - 1 - index

        # index 左右的三角形，有可能實際上是梯形但先計算三角形面積
        tri_lef = (n_lef * (n_lef + 1)) // 2
        tri_rit = (n_rit * (n_rit + 1)) // 2

        # case 1: 左右對稱
        if maxSum <= (tri_rit * 2 + n_rit + 1):
            return int(math.sqrt(maxSum)) + 1

        # case 2: 右邊為梯形
        if maxSum <= (tri_lef + tri_rit + (n_lef - n_rit) * n_rit + n_lef + 1):
            b = 3 + 2 * n_rit
            return int((-b + math.sqrt(b * b - 8 * (tri_rit + 1 - n_rit * n_rit - maxSum))) / 2) + 1 + 1

        # case 3: 兩邊為梯形
        maxSum -= (tri_lef + tri_rit + (n_lef - n_rit) * n_rit + n_lef + 1)
        return n_lef + 1 + 1 + (maxSum // n)