Namaran

Code daily. Without assist.

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] のような答えになります。