Pythonで左右の最も近い小さい要素間の最大差を求める方法

問題の概要

整数の配列が与えられたとき、各要素について「左側で最も近い小さい要素」と「右側で最も近い小さい要素」の絶対差を計算し、その最大値を求める問題です。ある要素の左側または右側により小さい要素が存在しない場合は、0 をその小さい要素として扱います。

例えば、入力が A = [3, 5, 9, 8, 8, 10, 4] の場合、出力は 4 になります。これは次のように計算されます。

• 左側の最も近い小さい要素 L = [0, 3, 5, 5, 5, 8, 3]
• 右側の最も近い小さい要素 R = [0, 4, 8, 4, 4, 4, 0]
• 最大絶対差 |L[i] − R[i]| = |8 − 4| = 4

アルゴリズム（解き方の手順）

この問題はスタックを活用することで効率的に解けます。手順は以下の通りです。

1. left_small_element() 関数を定義する

引数として配列 A と、結果を格納するための temp を受け取ります。

• n := 配列 A のサイズ
• stack := 空のリストを作成
• i を 0 から n−1 まで繰り返す：
  • スタックが空でなく、スタックの先頭要素が A[i] 以上である間、スタックから要素を取り除く（pop）
  • スタックが空でなければ、temp[i] := スタックの先頭要素
  • そうでなければ、temp[i] := 0
  • A[i] をスタックの末尾に追加

2. メイン処理

• n := 配列 A のサイズ
• left := サイズ n のリスト（すべて 0 で初期化）
• right := サイズ n のリスト（すべて 0 で初期化）
• left_small_element(A, left) を呼び出し、左側の結果を求める
• left_small_element(反転した A, right) を呼び出し、右側の結果を求める
• res := −1 で初期化
• i を 0 から n−1 まで繰り返し、res := max(res, |left[i] − right[n−1−i]|)

Pythonでの実装例

以下の実装を見ると、理解が深まります。

def left_small_element(A, temp):
    n = len(A)
    stack = []
    for i in range(n):
        while(stack != [] and stack[len(stack)-1] >= A[i]):
            stack.pop()
        if(stack != []):
            temp[i]=stack[len(stack)-1]
        else:
            temp[i]=0
        stack.append(A[i])

def find_maximum_difference(A):
    n = len(A)
    left=[0]*n
    right=[0]*n
    left_small_element(A, left)
    left_small_element(A[::-1], right)
    res = -1
    for i in range(n):
        res = max(res, abs(left[i] - right[n-1-i]))
    return res

A = [3, 5, 9, 8, 8, 10, 4]
print(find_maximum_difference(A))

入力

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

出力

4

計算量について

このアルゴリズムでは、各要素は最大でもスタックに一度 push され、一度 pop されるだけです。そのため、時間計算量は O(n)、空間計算量も O(n) となります。二重ループで左右それぞれの小さい要素を毎回探索する素朴な方法（O(n²)）と比べ、大きな配列でも高速に動作するのが特徴です。