Pythonで「最小値の2倍が最大値より大きい」条件を満たす最長の部分リストの長さを求めるプログラム

問題の概要

数値のリスト nums が与えられたとき、「部分リストの最小値の2倍が最大値より大きい」という条件(2 × 最小値 > 最大値)を満たす、最長の連続する部分リストの長さを求めることを考えます。

例えば、入力が nums = [10, 2, 6, 6, 4, 4] の場合、出力は 4 になります。これは、部分リスト [6, 6, 4, 4] が条件 (2×4) > 6 を満たす最長の部分リストだからです。

解決アプローチ:スライディングウィンドウ + モノトニックデック

この問題は、スライディングウィンドウ(尺取り法)とモノトニックデック(両端キュー)を組み合わせることで効率的に解けます。各ステップでの処理内容は以下の通りです。

• ret := 0(答えとなる最大長を保持)
• minq := 空の両端キュー(現在のウィンドウ内の最小値のインデックスを管理)
• maxq := 空の両端キュー(現在のウィンドウ内の最大値のインデックスを管理)
• l := 0(ウィンドウの左端)
• r := 0(ウィンドウの右端)

r が nums のサイズ未満である間、以下を繰り返します。

• n := nums[r]
• minq が空でなく、かつ n < nums[minqの末尾] の間、minq の末尾の要素を削除し、その後 r を minq の末尾に挿入(最小値用の単調増加キューを維持)
• maxq が空でなく、かつ n > nums[maxqの末尾] の間、maxq の末尾の要素を削除し、その後 r を maxq の末尾に挿入(最大値用の単調減少キューを維持)
• r := r + 1
• l < r かつ nums[minq[0]] * 2 <= nums[maxq[0]](条件を満たさない)の間:
  • minq[0] == l ならば、minq の先頭要素を削除
  • maxq[0] == l ならば、maxq の先頭要素を削除
  • l := l + 1(ウィンドウの左端を縮める)
• ret := max(ret, r - l)(現在のウィンドウ幅で答えを更新)

最後に ret を返します。各要素は高々1回ずつ追加・削除されるため、全体の計算量は O(n) となります。

実装例

それでは、実際のPythonコードを見てみましょう。

from collections import deque

def solve(nums):
    ret = 0
    minq, maxq = deque(), deque()
    l, r = 0, 0
    while r < len(nums):
        n = nums[r]
        while minq and n < nums[minq[-1]]:
            minq.pop()
        minq.append(r)
        while maxq and n > nums[maxq[-1]]:
            maxq.pop()
        maxq.append(r)
        r += 1
        while l < r and nums[minq[0]] * 2 <= nums[maxq[0]]:
            if minq[0] == l:
                minq.popleft()
            if maxq[0] == l:
                maxq.popleft()
            l += 1
        ret = max(ret, r - l)
    return ret

nums = [10, 2, 6, 6, 4, 4]
print(solve(nums))

入力

[10, 2, 6, 6, 4, 4]

出力

4

まとめ

このアルゴリズムでは、2つのモノトニックデックによってウィンドウ内の最小値・最大値を常にO(1)で参照できるようにしています。条件 2 × 最小値 ≤ 最大値 を満たす限り左端を進めてウィンドウを縮小し、条件を満たした時点でのウィンドウ幅の最大値を記録することで、線形時間で最長の部分リストの長さを求められます。