Pythonで「最小値×2＞最大値」を満たす最長の部分リストの長さを求めるプログラム

数値のリスト nums が与えられたとき、「部分リスト内の最小値 × 2 ＞ 部分リスト内の最大値」という条件を満たす、最長の連続した部分リスト（サブリスト）の長さを求める問題を考えてみましょう。

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

解法のアプローチ：スライディングウィンドウと単調両端キュー

この問題は、スライディングウィンドウ（尺取り法）と単調な両端キュー（deque）を組み合わせることで効率的に解けます。各時点でのウィンドウ内の最小値と最大値を O(1) で取得できるように、インデックスを管理する2つの両端キューを用意します。

アルゴリズムの手順

• 答えを格納する変数 ret を 0 で初期化します。
• 最小値用の両端キュー minq と、最大値用の両端キュー maxq を定義します。
• ウィンドウの左端 l と右端 r を 0 に初期化します。
• r がリストのサイズ未満である間、以下を繰り返します。
  • n := nums[r] とします。
  • minq が空でなく、かつ n が minq の末尾が指す値より小さい間、minq の末尾を削除します。
  • r を minq の末尾に追加します。
  • maxq が空でなく、かつ n が maxq の末尾が指す値より大きい間、maxq の末尾を削除します。
  • r を maxq の末尾に追加します。
  • r を 1 増やします。
  • l < r かつ「minq の先頭の値 × 2 ≤ maxq の先頭の値」（条件を満たさない）である間、以下を繰り返します。
    • minq の先頭が l と同じなら、その先頭を削除します。
    • maxq の先頭が l と同じなら、その先頭を削除します。
    • l を 1 増やしてウィンドウを縮小します。
  • ret を ret と (r - l) の大きい方で更新します。
• 最後に ret を返します。

この方法では、各要素が高々1回ずつ追加・削除されるため、全体の計算量は O(n) となり、非常に効率的です。

実装例

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

class Solution:
    def solve(self, nums):
        from collections import deque
        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

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

入力

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

出力

4

まとめ

このプログラムでは、単調両端キューを使うことでウィンドウ内の最小値・最大値を常に高速に参照でき、条件を満たさなくなった瞬間に左端を進めてウィンドウを調整しています。結果として、線形時間 O(n) で最長の部分リストの長さを求めることができます。同様のテクニックは「スライディングウィンドウ最大値」などの古典的な問題にも応用できるので、ぜひ覚えておきましょう。