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 次浏览

开启你的职业生涯

完成课程获得认证

开始学习
广告