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.last() {
if xs[top] >= x {
break;
}
ans[top] = Some(x);
stack.pop();
}
stack.push(i);
}
ans
}
fn main() {
println!("{:?}", next_greater(&[2, 7, 3, 5, 4, 6, 1]));
}
これは何を出力するでしょうか?
Answer
[Some(7), None, Some(5), Some(6), Some(6), None, None] と出力されます。
stack には、まだ自分より大きい値に出会っていない要素のインデックスが積まれています。新しい値 x が来るたびに、スタックの上から x より小さい要素を取り出し、その答えを x にします。取り出しが止まった時点で残っている要素は x 以上なので、スタックの値は下から上へ向かって大きくならない並びに保たれます。
[2, 7, 3, 5, 4, 6, 1] で追うと、7 が 2 を、5 が 3 を取り出し、6 は 4 と 5 をまとめて取り出します。最後まで残る 7、6、1 は右に大きい値がないので、None のままです。各インデックスは1回積まれて高々1回取り出されるので、二重ループに見えても、全体の手間は要素数に比例します。