在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之间变化，递减1，执行以下操作：
- 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 := max(lmax[i], rmax[i + k + 1]) – min(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))