【Python】リストの要素を最大3回変更して、最大値と最小値の差を最小化する方法

数値のリスト nums が与えられます。ここでは「ある要素を任意の値に書き換える」という操作を最大3回まで実行できるものとし、操作後のリストにおける最大値と最小値の差（レンジ）を最小化することを目指します。

例えば、入力が nums = [2, 3, 4, 5, 6, 7] の場合、出力は 2 になります。これは、リストを [4, 3, 4, 5, 4, 4] のように書き換えることで、最大値 5 から最小値 3 を引いた差が 2 になるためです。

解決のためのアプローチ

この問題を解く鍵となるのは、次のような発想です。

• 3つの要素を自由に書き換えられるということは、実質的に「ソート済みリストの先頭または末尾側から合計3個を取り除き、残った要素だけを考える」ことと同じです。
• 残す要素の組み合わせは、先頭から0個・1個・2個・3個を除外する4通りしかありません。
• したがって、リストをソートした後、各ケースでの最大値と最小値の差を計算し、そのうち最も小さい値を返せばよいことになります。

アルゴリズムの手順

1. nums のサイズが4以下の場合、すべての要素を同じ値に揃えられるため、0 を返します。
2. n に nums のサイズを代入します。
3. リスト nums を昇順にソートします。
4. i を 0 から 3 まで動かしながら nums[n-4+i] - nums[i] の差を計算し、その最小値を返します。

実装例

以下のコードで具体的な動作を確認しましょう。

class Solution:
   def solve(self, nums):
      if len(nums) <= 4:
         return 0
      nums.sort()
      return min(nums[-4 + i] - nums[i] for i in range(4))

ob = Solution()
nums = [2, 3, 4, 5, 6, 7]
print(ob.solve(nums))

入力

[2, 3, 4, 5, 6, 7]

出力

2

まとめ

このアルゴリズムの時間計算量は、ソート処理が支配的となるため O(n log n) であり、追加のメモリはほぼ不要で空間計算量は O(1) です。なお、i=0 の場合は末尾3個を除外、i=3 の場合は先頭3個を除外することに対応しており、それぞれ「先頭から k 個・末尾から (3−k) 個を除外する」全パターンを網羅しています。この考え方は「k 回の変更で範囲を最小化する」という問題への一般化にも応用できるので、ぜひ押さえておきましょう。