Namaran

Code daily. Without assist.

2026-10-29

next_greater.rs

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

fn main() {
    println!("{:?}", next_greater(&[2, 7, 3, 1, 5]));
}

スライスの各要素について、右側にある最初の、その要素より大きい値を求め、無ければ None にする next_greater です。next_greater(&[2, 7, 3, 1, 5]) は本来 [Some(7), None, Some(5), Some(5), None] を返すはずが、いまは [Some(7), None, None, Some(5), None] を返し、右に5がある3の答えが None になります。

Answer

Wrong

        while let Some(top) = stack.pop()
            && v[top] < x
        {
            ans[top] = Some(x);
        }

while let の条件は左から評価され、&& の後半を調べる前に stack.pop() がもう実行されています。v[top] < x が偽になって繰り返しが終わるとき、取り出した top はどこにも戻されず、stack から消えます。x より大きい値はまだ答えが決まっていないのに、以後どの要素とも比べられません。

入力例では、7を積んだあと3が来ると、7を取り出して 7 < 3 が偽になり、7が消えます。7の答えは None が正しいので、ここでは症状が出ません。次の1が来ると3が同じように消え、そのあと5が来ても3は stack に無いので、ans[2] は None のまま残ります。stack の中で答えを待っている要素が、自分より小さい要素が来るたびに1つずつ失われていきます。

Right

        while let Some(&top) = stack.last()
            && v[top] < x
        {
            stack.pop();
            ans[top] = Some(x);
        }

条件では stack.last() で一番上を覗くだけにし、取り出すのは v[top] < x が真だと分かってから本体の中で行います。条件が偽になっても stack は変わらないので、3は1の下に残り、5が来たときに1に続いて取り出されて ans[2] が Some(5) になります1。

  1. while let や if let の条件を && でつなぐ書き方(let chains)は、Rust 2024 エディションで使えるようになりました。条件は左から順に評価され、途中で偽になればそこで止まりますが、それより前に評価した式の副作用は取り消されません。