Python程式：刪除k個數字後查詢相鄰值的最大差值

假設我們有一個名為nums的數字列表，它們按升序排序，我們必須從列表中刪除k個值，以便任何兩個相鄰值之間的最大差值儘可能小，最後找到該差值。

因此，如果輸入類似於nums = [15, 20, 30, 400, 1500] k = 2，則輸出將為10，因為如果我們刪除[400, 1500]，則得到20和30的差值。

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

  • abs_diff := nums中每個連續元素的差值列表
  • 定義函式dp()。這將接收i、j、cnt
  • 如果cnt等於0，則
    • m := 0
    • 對於範圍從i到j的k，執行：
      • m := m和abs_diff[k]中的最大值
    • 返回m
  • 返回dp(i + 1, j, cnt - 1)和dp(i, j - 1, cnt - 1)中的最小值
  • 從主方法執行以下操作：
  • 返回dp(0, abs_diff的大小 - 1, k)

讓我們看下面的實現來更好地理解：

示例

線上演示

class Solution:
   def solve(self, nums, k):
      abs_diff = [nums[i] - nums[i - 1] for i in range(1, len(nums))]

      def dp(i, j, cnt):
         if cnt == 0:
            m = 0
            for k in range(i, j + 1):
               m = max(m, abs_diff[k])
            return m
         return min(dp(i + 1, j, cnt - 1), dp(i, j - 1, cnt - 1))

      return dp(0, len(abs_diff) - 1, k)
     
ob = Solution()
nums = [15, 20, 30, 400, 1500]
k = 2
print(ob.solve(nums, k))

輸入

[15, 20, 30, 400, 1500], 2

輸出

10

更新於：2020年12月2日

174 次瀏覽

開啟你的職業生涯

完成課程獲得認證

開始學習
廣告