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() はスタックを空になるまで回すときの定番の形ですが、途中で止まることのあるループで使うと、止まった回の要素を失います。