Pythonで解く「最小範囲 I」問題：配列の最大値と最小値の差を最小化する方法

問題概要

整数からなる配列 A が与えられます。各要素 A[i] に対して、範囲 [-K, K] 内の任意の値 x を選び、それを A[i] に加算することができます。この操作をすべての要素に適用した結果として得られる新しい配列を B とします。このとき、B の最大値と最小値の差が取りうる最小値を求めてください。

例えば、入力が A = [0, 10]、K = 2 の場合を考えてみましょう。操作後の配列を B = [2, 8] とすることができ、最大値 8 と最小値 2 の差は 6 となるため、出力は 6 になります。

アプローチ

この問題は実は非常にシンプルです。ポイントは次の通りです。

• 最大値をできるだけ小さくしたいなら、配列 A の最大値から K を引くのが最善
• 最小値をできるだけ大きくしたいなら、配列 A の最小値に K を足すのが最善
• K が十分大きくて差が負になる場合、すべての要素を同じ値に揃えられるため、答えは 0

以上をまとめると、次の手順で解くことができます。

• MAX := （A の最大値）− K
• MIN := （A の最小値）＋ K
• difference := MAX − MIN
• difference < 0 の場合は 0 を返す
• それ以外の場合は difference を返す

Pythonでの実装例

class Solution:
    def smallestRangeI(self, A, K):
        MAX = max(A) - K
        MIN = min(A) + K
        difference = MAX - MIN
        if difference < 0:
            return 0
        else:
            return difference

ob = Solution()
print(ob.smallestRangeI([0, 10], 2))

入力例

[0, 10], 2

出力例

6

計算量の目安

max() と min() による配列の走査がそれぞれ O(N) であるため、全体の時間計算量は O(N) となります。また、追加のメモリはほとんど不要で、空間計算量は O(1) です。

注目すべきは、答えに関係するのは配列内の「最大値」と「最小値」だけであり、それ以外の要素の値は結果に一切影響しないという点です。一見複雑そうに見える問題でも、本質を見抜けば定数個の値だけで解ける良い例と言えるでしょう。