Python程序：删除K长度子列表后查找最小振幅

假设我们有一个名为nums的数字列表和一个值k。首先，我们将删除大小为k的子列表，然后找到(nums的最大值 - nums的最小值)的最小值。

因此，如果输入类似于nums = [2, 3, 10, 9, 8, 4] k = 3，则输出将为2。如果我们删除[10, 9, 8]，我们将得到[2, 3, 4]，而4 - 2 = 2

为了解决这个问题，我们将遵循以下步骤：

  • N := nums的大小

  • 将nums复制到lmin和lmax

  • 同样将nums复制到rmin和rmax

  • 对于i从1到N-1，执行以下操作：

    • lmin[i] := lmin[i]和lmin[i-1]的最小值

    • lmax[i] := lmax[i]和lmax[i-1]的最大值

  • 对于i从N-2到0递减，执行以下操作：

    • rmin[i] := rmin[i]和rmin[i+1]的最小值

    • rmax[i] := rmax[i]和rmax[i+1]的最大值

  • ans := (rmax[k] - rmin[k])、(lmax[k的补集] - lmin[k的补集])的最小值

  • 对于i从0到N-k-2，执行以下操作：

    • cand := (lmax[i]和rmax[i+k+1]的最大值) - (lmin[i]和rmin[i+k+1]的最小值)

    • ans := ans和cand的最小值

  • 返回ans

示例

让我们看看下面的实现以更好地理解

def solve(nums, k):
   N = len(nums)
   lmin, lmax = nums[:], nums[:]
   rmin, rmax = nums[:], nums[:]
   for i in range(1, N):
      lmin[i] = min(lmin[i], lmin[i - 1])
      lmax[i] = max(lmax[i], lmax[i - 1])
   for i in range(N - 2, -1, -1):
      rmin[i] = min(rmin[i], rmin[i + 1])
      rmax[i] = max(rmax[i], rmax[i + 1])

   ans = min(rmax[k] - rmin[k], lmax[~k] - lmin[~k])
   for i in range(N - k - 1):
      cand = max(lmax[i], rmax[i + k + 1]) - min(lmin[i], rmin[i + k + 1])
      ans = min(ans, cand)

   return ans

nums = [2, 3, 10, 9, 8, 4]
k = 3
print(solve(nums, k))

输入

[2, 3, 10, 9, 8, 4], 3

输出

2

更新于：2021年10月12日

217 次浏览

启动您的职业生涯

完成课程获得认证

开始学习
广告