Pythonで「毎日の気温」問題を解く：単調スタックを使った効率的なアルゴリズム

問題の概要

毎日の気温を表すリスト T が与えられたとします。このとき、入力の各日について「より暖かい気温になるまで何日待つ必要があるか」を示すリストを返すことが求められます。将来により暖かい日が存在しない場合は、代わりに 0 を格納します。

例えば、T = [73, 74, 75, 71, 69, 72, 76, 73] の場合、出力は [1, 1, 4, 2, 1, 1, 0, 0] となります。

この問題は、単調スタック（Monotonic Stack）と呼ばれるテクニックを使うことで、効率的に解くことができます。

解法のアプローチ

具体的な手順は以下の通りです。

• ans := T と同じサイズの配列を作成し、すべて 0 で初期化する
• スタックを1つ定義し、0 を挿入する。また i := 1 とする
• i が T の長さ未満である間、以下を繰り返す
  • スタックが空でなく、かつ T[i] > T[スタックの先頭要素] である間、以下を繰り返す
    • index := スタックの先頭要素
    • ans[index] := i − index
    • スタックから先頭要素を削除する
  • スタックの長さが 0、または T[i] <= T[スタックの先頭要素] の場合
    • i をスタックに挿入する
  • i を 1 増やす
• ans を返す

Pythonでの実装例

以下の実装を見ると、処理の流れがより理解しやすくなります。

class Solution(object):
    def dailyTemperatures(self, T):
        ans = [0 for i in range(len(T))]
        stack = []
        stack.append(0)
        i = 1
        while i < len(T):
            while len(stack) and T[i] > T[stack[-1]]:
                index = stack[-1]
                ans[index] = i - index
                stack.pop()
            if not len(stack) or T[i] <= T[stack[-1]]:
                stack.append(i)
            i += 1
        return ans

ob1 = Solution()
print(ob1.dailyTemperatures([73, 74, 75, 71, 69, 72, 76, 73]))

入力

[73, 74, 75, 71, 69, 72, 76, 73]

出力

[1, 1, 4, 2, 1, 1, 0, 0]

計算量について

このアルゴリズムの時間計算量は O(n) です。各インデックスは最大でもスタックに1回プッシュされ、1回ポップされるだけだからです。素朴な二重ループによる O(n²) の解法と比べて大幅に高速化できます。空間計算量も O(n) となり、スタックと結果配列の分の領域が必要になります。