Namaran

Code daily. Without assist.

2026-09-17

next_greater.rs

fn next_greater(xs: &[i32]) -> Vec<Option<i32>> {
    let mut ans = vec![None; xs.len()];
    let mut stack: Vec<usize> = Vec::new();
    for (i, &x) in xs.iter().enumerate() {
        while let Some(top) = stack.pop() {
            if xs[top] >= x {
                break;
            }
            ans[top] = Some(x);
        }
        stack.push(i);
    }
    ans
}

fn main() {
    println!("{:?}", next_greater(&[5, 3, 4, 6]));
}

next_greater は、各要素より右にある最初の大きい値を、あれば Some、なければ None として並べて返すつもりの関数です。入力は next_greater(&[5, 3, 4, 6])。いまの出力は [None, Some(4), Some(6), None] ですが、本来の出力は [Some(6), Some(4), Some(6), None] です。本来の出力になるよう直してください。

Answer

while let Some(top) = stack.pop() は、条件を調べるより先に要素をスタックから取り出します。xs[top] >= x で break するとき、その top はもうスタックにありません。まだ自分より大きい値に出会っていない要素が、答えをもらえないまま消えてしまいます。

[5, 3, 4, 6] で追うと、3 が来たときに 5 のインデックスが取り出され、5 >= 3 で break します。5 はここで落ちます。6 が来たときにはスタックに 5 がないので、ans[0] は None のままです。症状は 6 を処理した結果に出ますが、原因は 3 を処理したときの break にあります。

最小の修正は、break の前に、取り出した要素を積み直すことです。

            if xs[top] >= x {
                stack.push(top);
                break;
            }

取り出さずに覗く形へ書き換えてもかまいません。while let Some(&top) = stack.last() で上の要素を見て、答えを書いたあとで stack.pop() を呼べば、条件を満たさなかった要素は最初からスタックに残ります。while let Some(x) = stack.pop() はスタックを空になるまで回すときの定番の形ですが、途中で止まることのあるループで使うと、止まった回の要素を失います。