Pythonで長さkの部分リストを1つ削除した後の最小振幅を求めるプログラム

数値のリスト nums と整数 k が与えられます。まずサイズ k の部分リスト（連続する区間）をひとつだけ取り除いたとき、残ったリストにおける「最大値 − 最小値」、すなわち振幅（amplitude）が最も小さくなるような削除方法を求めます。

問題の具体例

たとえば nums = [2, 3, 10, 9, 8, 4]、k = 3 の場合を考えてみます。[10, 9, 8] を取り除くと、残りのリストは [2, 3, 4] となり、振幅は 4 − 2 = 2 になります。これがこの入力に対する答えです。

解法のアプローチ

すべての削除位置について毎回最大値と最小値を計算し直すと、計算量は O(N × k) になり非効率です。そこで、左側からの累積最大・最小（lmax / lmin）と右側からの累積最大・最小（rmax / rmin）を事前に計算しておくことで、各削除位置における振幅を O(1) で求められるようにします。全体の計算量は O(N) です。

アルゴリズムの手順

• N := nums のサイズとする

• nums を lmin と lmax にコピーする

• 同様に、nums を rmin と rmax にもコピーする

• i が 1 から N − 1 までの範囲で：

  • lmin[i] := min(lmin[i], lmin[i − 1])

  • lmax[i] := max(lmax[i], lmax[i − 1])

• i が N − 2 から 0 まで減少しながら：

  • 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])　※先頭 k 個、または末尾 k 個を削除するケースに対応

• i が 0 から N − k − 2 までの範囲で：

  • cand := max(lmax[i], rmax[i + k + 1]) − min(lmin[i], rmin[i + k + 1])

  • ans := min(ans, cand)

• ans を返す

ここで ~k はビット反転演算子で、~k == -(k + 1) となるため、lmax[~k] はリスト末尾から k + 1 番目の要素、すなわち lmax[N − k − 1] を意味します。先頭や末尾ではなく中間の区間を削除する場合は、削除区間の直前までの累積情報（lmin / lmax）と、削除区間の直後からの累積情報（rmin / rmax）を組み合わせて振幅を求めます。

Pythonでの実装例

以下のコードで実際の動作を確認できます。

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

まとめ

この問題は、左右両方向からの累積最大値・最小値を前計算しておくテクニック（プレフィックス／サフィックス処理）によって、素朴な全探索よりも大幅に効率化できます。時間計算量 O(N)、空間計算量 O(N) であり、リストのサイズが大きくなっても実用的な速度で動作します。類似の「区間削除後に統計量を最小化する」問題にも応用できる汎用的なパターンなので、ぜひ覚えておきましょう。