Namaran

Code daily. Without assist.

2026-09-17

days_until_warmer.rs

fn days_until_warmer(temps: &[i32]) -> Vec<usize> {
}

日ごとの気温 temps を受け取り、各日について、その日より気温が高い日が何日後に来るかを並べた Vec を返す days_until_warmer を書いてください。そういう日が来なければ 0 です。同じ気温は「高い」に含めません。空の入力には空の Vec を返します。days_until_warmer(&[73, 74, 75, 71, 69, 72, 76, 73]) → [1, 1, 4, 2, 1, 1, 0, 0]、days_until_warmer(&[5, 5]) → [0, 0]、days_until_warmer(&[]) → []

Reference
fn days_until_warmer(temps: &[i32]) -> Vec<usize> {
    let mut ans = vec![0; temps.len()];
    let mut stack: Vec<usize> = Vec::new();
    for (i, &t) in temps.iter().enumerate() {
        while let Some(&j) = stack.last()
            && temps[j] < t
        {
            ans[j] = i - j;
            stack.pop();
        }
        stack.push(i);
    }
    ans
}

まだ答えの決まっていない日のインデックスをスタックに積んでおき、新しい日 i の気温 t がスタックの上の日 j より高いあいだ、j を取り出して i - j を答えにします。スタックに気温ではなくインデックスを積むのは、日数を出すのに位置が要るからです。気温のほうは temps[j] で引けます。

ループの条件は、Rust 2024 で使えるようになった let チェーンで書いています。while let Some(&j) = stack.last() && temps[j] < t は、「スタックに要素があり、しかもその日が t より寒い」ときだけ本体に入ります。last() は覗くだけで取り出さないので、条件を満たさなかった要素はスタックに残ります。&j のパターンで usize をコピーして受け取っているため、本体で stack.pop() を呼んでも借用はぶつかりません。

比較が < なので、[5, 5] の2つ目の 5 は1つ目を取り出さず、どちらも 0 のままです。これは参考実装で、唯一の正解ではありません。let チェーンを使わずに while let の中で if と break を書いても、右端から走査してスタックに候補を残していく書き方でも、同じ結果になります。