C++で解く「毎日の気温」問題：スタックを使って次に暖かい日までの日数を効率的に計算する方法

問題の概要

正の気温を表す配列 T が与えられているとします。この課題では、リスト内の各気温について、「次により暖かい気温が現れるまでの日数」を計算します。

例

入力： T = [73, 74, 75, 71, 69, 72, 76, 73]

出力： [1, 1, 4, 2, 1, 1, 0, 0]

説明： 気温のリスト [73, 74, 75, 71, 69, 72, 76, 73] の場合、0日目（73度）の次に暖かい日は1日目（74度）なので、答えは 1 になります。同様に、6日目（76度）はリスト全体で最も暖かいため、それ以降に暖かい日は存在せず 0 となります。したがって、最終的な出力は [1, 1, 4, 2, 1, 1, 0, 0] になります。

この問題へのアプローチ

気温のリストが与えられ、各日から「次に暖かい日」までの日数を求める必要があります。

この問題は スタック を使うことで効率的に解くことができます。最初はスタックは空の状態です。スタックが空であれば、その日のインデックスをプッシュします。そして、スタックのトップにある気温が現在の気温より低い（＝より寒い）場合は、「その日にとって次に暖かい日が見つかった」ことを意味するため、スタックからポップします。

さらに、スタックのトップの気温がまだ現在の気温より低いかどうかを繰り返し確認し、該当する場合はインデックスの差から日数を計算して結果に格納します。この手法は「単調スタック（Monotonic Stack）」と呼ばれる定番テクニックです。

• 気温データを入力として受け取ります。
• 整数関数 dailyTemperature(int *T) は気温配列を入力とし、次に暖かい気温までの日数のリストを返します。
• 気温配列を先頭から順に走査します。
• すべての結果を格納するための結果ベクトルまたは配列を作成します。
• 空のスタックを用意し、スタックのトップの気温が T[i] より低い間はポップして日数を計算し、その後現在のインデックスをプッシュします。
• 結果を保存して返します。

このアルゴリズムの計算量は O(n) です。各インデックスは最大でも1回プッシュされ、1回ポップされるだけだからです。すべての組み合わせを調べる O(n²) の二重ループに比べて、はるかに効率的です。

コード例

#include<bits/stdc++.h>
using namespace std;
void dailyTemp(int * T, int n) {
   stack < int > s;
   int ans[n];
   memset(ans, 0, sizeof(ans));
   for (int i = 0; i < n; i++) {
      while (!s.empty() && T[s.top()] < T[i]) {
         int j = s.top();
         s.pop();
         ans[j] = i - j;
      }
      s.push(i);
   }
   for (int i = 0; i < n; i++) {
      cout << ans[i] << " ";
   }
}
int main() {
   int n = 8;
   int T[8] = {73, 74, 75, 71, 69, 72, 76, 73};
   dailyTemp(T, n);
   return 0;
}

出力

上記のコードを実行すると、次の出力が得られます。

1 1 4 2 1 1 0 0

この結果から、たとえば2日目（75度）の次に暖かい気温は4日後の6日目（76度）であることが読み取れます。また、7日目（73度）以降にそれを上回る気温は存在しないため、末尾は 0 になっています。