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