PythonでKLengthサブリストを削除した後に最小振幅を見つけるプログラム

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の補数]）

• 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))

入力

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

出力

2