Pythonで配列の最大幅ランプを見つける方法：アルゴリズムと実装例

ランプ（ramp）とは？

整数の配列 nums が与えられたとき、「ランプ」とは i < j かつ nums[i] <= nums[j] を満たすインデックスのペア (i, j) のことです。ランプの幅は j − i で表されます。この記事では、nums に含まれるランプの中で最大の幅を求める方法を解説します。条件を満たすペアがひとつも存在しない場合は 0 を返します。

例として、nums = [6,0,8,2,1,5] という入力を考えてみましょう。この場合の出力は 4 になります。(i, j) = (1, 5) のとき nums[1] = 0、nums[5] = 5 となり、条件を満たす幅 5 − 1 = 4 のランプが得られるためです。

解法の考え方

この問題は、次の手順で解くことができます。

1. 辞書 B を作成し、各値に対してその値が出現するインデックスの一覧を登録します。i 番目の要素を x = nums[i] とするとき、x がすでに B に存在すれば B[x] の末尾に i を追加し、存在しなければ B[x] = [i] とします。
2. mini を [inf]（正の無限大）、maxi を [-inf]（負の無限大）でそれぞれ初期化します。
3. B のキーを昇順に処理し、「mini の末尾の値」と「B[x] の最小値」のうち小さい方を mini に追記します。これにより、各値 x について「x 以下の値が現れる最も左のインデックス」が記録されていきます。
4. 続いて B のキーを降順に処理し、「maxi の末尾の値」と「B[x] の最大値」のうち大きい方を maxi に追記します。これにより、各値 x について「x 以上の値が現れる最も右のインデックス」が記録されます。
5. maxi を逆順に並べ替えて末尾の初期値を取り除き、mini は先頭の初期値を取り除きます。こうすると、昇順の各キー x に対して「x 以下の最小インデックス（mini）」と「x 以上の最大インデックス（maxi）」が同じ位置で対応します。
6. p = 0、res = -inf とし、p が mini の長さに達するまで res = max(res, maxi[p] − mini[p]) を繰り返しながら p を進めます。
7. 最終的な res を答えとして返します。

Pythonによる実装例

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

def solve(nums):
    B = {}
    for i in range(len(nums)):
        x = nums[i]
        if x in B:
            B[x].append(i)
        else:
            B[x] = [i]

    mini = [float('inf')]
    maxi = [float('-inf')]
    for x in sorted(B.keys()):
        mini.append(min(mini[-1], min(B[x])))

    for x in sorted(B.keys(), reverse=True):
        maxi.append(max(maxi[-1], max(B[x])))

    maxi = maxi[::-1][:-1]
    mini = mini[1:]

    p = 0
    res = float('-inf')
    while p < len(mini):
        res = max(res, maxi[p] - mini[p])
        p += 1

    return res


nums = [6, 0, 8, 2, 1, 5]
print(solve(nums))

入力

[6, 0, 8, 2, 1, 5]

出力

4

まとめ

値ごとの出現位置を辞書に記録し、累積最小値と累積最大値を組み合わせることで、すべてのペアを総当たりすることなく最大幅ランプを効率的に求められます。計算量は O(n log n)（ソート部分が支配的）となり、二重ループによる O(n²) の素朴な解法と比べて大幅に高速です。大きな配列を扱う場合にも実用的なアプローチといえるでしょう。