Python 中删除 KLength 子列表后查找最小振幅的程序

pythonserver side programmingprogramming更新于 2025/12/24 16:12:17

假设我们有一个名为 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 中
对于范围为 1 到 N - 1 的 i，执行
- lmin[i] := lmin[i] 和 lmin[i - 1] 中的最小值
- lmax[i] := lmax[i] 和 lmax[i - 1] 中的最大值
对于 N - 2 到 0 范围内的 i，减少 1，然后执行
- rmin[i] := rmin[i] 和 rmin[i + 1] 中的最小值
- rmax[i] := rmax[i] 和 rmax[i + 1] 中的最大值
ans := (rmax[k] - rmin[k]) 中的最小值，(lmax[k 的补集] - lmin[k 的补集k])
对于 0 到 N - k - 2 范围内的 i，执行
- 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))