Python程式：在有界陣列中查詢給定索引處的最大值

假設我們有三個值：n、index和maxSum。考慮一個名為nums的陣列，我們需要找到nums[index]，並且nums滿足以下條件：

  • nums的大小為n

  • n中的所有元素都為正數。

  • |nums[i] - nums[i+1]| <= 1 對於所有i，0 <= i < n-1。

  • nums所有元素的和不超過maxSum。

  • nums[index]最大化。

因此，如果輸入類似於n = 6，index = 3，maxSum = 8，則輸出將為2，因為我們可以得到一個像[1,2,2,2,1,1]這樣的陣列，它滿足所有條件，並且這裡的nums[3]最大化。

為了解決這個問題，我們將遵循以下步驟：

  • left := maxSum/n 的商，right := maxSum + 1

  • ans := 0

  • 當left < right時，執行以下操作：

    • mid := left + (right-left)/2 的商

    • ind_l := (mid-1 + max(1, (mid-index))) * min(index, (mid-1))/2 的商 + |min(0, mid-index-1)|

    • ind_r := (mid + max(1, (mid-(n-index-1)))) * min(n-index, mid)/2 的商 + |min(0, mid-(n-index-1)-1)|

    • 如果ind_l + ind_r <= maxSum，則：

      • ans := mid

      • left := mid+1

    • 否則：

      • right := mid

  • 返回ans

示例

讓我們看下面的實現，以便更好地理解：

def solve(n, index, maxSum):
   left, right = maxSum//n, maxSum+1
   ans = 0
   while(left<right):
      mid = left + (right-left)//2
      ind_l = (mid-1+max(1,mid-index))*min(index,mid-1)//2 + abs(min(0,mid-index-1))
      ind_r = (mid+max(1,mid-(n-index-1)))*min(n-index, mid)//2+ abs(min(0,mid-(n-index-1)-1))

      if ind_l + ind_r <=maxSum:
         ans = mid
         left = mid+1
      else:
         right = mid
   return ans

n = 6
index = 3
maxSum = 8
print(solve(n, index, maxSum))

輸入

6, 3, 8

輸出

2

更新於：2021年10月7日

瀏覽量：308

開啟您的職業生涯

完成課程獲得認證

開始學習
廣告