2026-10-29
next_greater_rev.rs
fn main() {
let v = [3, 1, 4, 1, 5];
let mut ans = vec![-1; v.len()];
let mut stack: Vec<i32> = Vec::new();
for (i, &x) in v.iter().rev().enumerate() {
while stack.last().is_some_and(|&top| top <= x) {
stack.pop();
}
if let Some(&top) = stack.last() {
ans[i] = top;
}
stack.push(x);
}
println!("{ans:?}");
}
これは何を出力するでしょうか?
Answer
[-1, 5, 5, 4, 4] です。
ループは v を右端から左へ読み、stack には、いま見ている値より右にある値のうち、まだ候補として残っているものが積まれています。新しい値 x が来ると、x 以下の値を上から取り除きます。それらは x の陰に隠れ、x より左の要素から見て「右側にある最初の大きい値」になることはもうないからです。取り除いたあとに残った一番上の値が x の右側にある最初の大きい値で、stack が空なら ans の -1 がそのまま残ります。v の右端から順に、5は空なので-1、1は5、4は1を取り除いて5、2つ目の1は4、3は1を取り除いて4です。
これらを ans のどこに書くかは i が決めます。v.iter().rev().enumerate() は、逆順に並べ替えたあとの列に0から番号を振るので、i は v の添字ではなく、右端から数えた順番です。右端の5の答えが ans[0] に、左端の3の答えが ans[4] に入り、ans は v と左右が逆の並びになります。
i を v の添字と読むと、各要素の位置に答えが入った [4, 4, 5, 5, -1] と答えてしまいます。もとの添字を保ったまま逆順に読むには、v.iter().enumerate().rev() と、番号を振ってから逆にします。逆に番号の振り方だけに目を向け、スタックが左側の値を探すと読むと、v の左から順に並べた [-1, 3, -1, 4, -1] を逆にした [-1, 4, -1, 3, -1] のような答えになります。