PythonでK個の要素を削除した後に最小振幅を求める方法

問題の概要

数値のリスト nums と整数 k が与えられます。nums からちょうど k 個の要素を削除したとき、残りの要素における「最大値 − 最小値」の差（振幅）が最小になるようにするには、どの要素を削除すればよいのでしょうか。

たとえば、入力が nums = [4, 10, 3, 2, 8, 9]、k = 3 の場合、出力は 2 になります。10・8・9 を削除すると残りは [2, 3, 4] となり、最大値は 4、最小値は 2 なので、差は 2 になるためです。

解法のアプローチ

この問題は「ソート＋スライディングウィンドウ」の考え方で効率的に解けます。k 個の要素を削除すると n − k 個の要素が残るため、ソート済みのリスト上で「連続する n − k 個の要素」からなるウィンドウをすべて調べ、その中で幅（最大値 − 最小値）が最も小さいものを見つければよいことになります。

具体的な手順は以下の通りです。

• リスト nums を昇順にソートする
• p := nums のサイズ − k（残す要素の個数）
• m := nums の最後の要素 − nums[0]（初期値としてリスト全体の振幅を設定）
• i を 0 から nums のサイズ − p まで 1 ずつ増やしながら繰り返す
  • もし nums[i + p − 1] − nums[i] < m ならば、m := nums[i + p − 1] − nums[i] と更新する
• m を返す

実装例

理解を深めるために、以下のPythonコードを見てみましょう。

def solve(nums, k):
   nums = sorted(nums)
   p = len(nums) - k
   m = nums[-1] - nums[0]
   for i in range(0, len(nums) - p + 1):
      if nums[i + p - 1] - nums[i] < m:
         m = nums[i + p - 1] - nums[i]
   return m

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

入力

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

出力

2

計算量について

ソートに O(n log n)、その後のウィンドウ走査に O(n) かかるため、全体の時間計算量は O(n log n) です。また、sorted() が新しいリストを作成するため、空間計算量は O(n) となります。すべての削除パターンを総当たりで試すアプローチ（O(C(n, k))）と比べて非常に効率的であり、大きな入力に対しても実用的な解法といえます。