Namaran

Code daily. Without assist.

2026-10-29

visible.rs

fn visible(heights: &[u32]) -> Vec<usize> {
}

左から右へ一列に並んだ人の背の高さ heights を受け取り、各人が右を向いたときに見える人数を並べた Vec を返す visible を書いてください。背の高さはすべて異なります。i 番目の人から右の j 番目の人が見えるのは、2人の間にいる全員が、2人のうち低いほうより低いときです。隣の人はいつも見えます。全体の計算時間は人数に比例する程度に収め、heights が空なら空の Vec を返します。

入力例 1

visible(&[10, 6, 8, 5, 11, 9])

出力例 1

[3, 1, 2, 1, 1, 0]

入力例 2

visible(&[4, 3, 2, 1])

出力例 2

[1, 1, 1, 0]

入力例 3

visible(&[])

出力例 3

[]
Reference
fn visible(heights: &[u32]) -> Vec<usize> {
    let mut seen = vec![0; heights.len()];
    let mut stack: Vec<u32> = Vec::new();
    for (i, &h) in heights.iter().enumerate().rev() {
        while stack.last().is_some_and(|&top| top < h) {
            stack.pop();
            seen[i] += 1;
        }
        if !stack.is_empty() {
            seen[i] += 1;
        }
        stack.push(h);
    }
    seen
}

i 番目の人より右で、i 番目の人との間にいる誰よりも高い人を左から順に拾うと、背の高さが増えていく列になります。間にそれより高い人がいれば、その人に隠れて誰からも見えないので、i 番目の人から見える候補はこの列の人だけです。列のうち i 番目の人より低い人は全員見えます。間にいるのはその人より低い人だけだからです。その先の、i 番目の人より高い最初の人も、間の全員が i 番目の人より低いので見えます。そこから先は、その人が i 番目の人より高いので、誰も見えません。見える人数は「列のうち自分より低い人の数」に、自分より高い人がいれば1を足したものです。

参考実装は右端から左へ進み、stack にこの列を、一番上が一番近い人になるように持ちます。h の人を加えるときは、h より低い人を上から取り除きながら数えます。取り除いた人は見える人そのもので、このあと h の人に隠れて、左の誰からも候補になりません。残った一番上の人は h の人の右側にいる最初の高い人で、stack が空でなければ1を足します。最後に h を積めば、stack は1人左から見た列になります。各人は1回積まれて高々1回取り除かれるので、繰り返しの回数は全体で人数の2倍以内です。

掲載したのは参考実装で、唯一の正解ではありません。左から右へ進み、新しく来た人から見て、取り除いた人と取り除いたあとの一番上の人の見える人数を1ずつ増やす書き方もあります。2人ずつ間を調べる書き方は、答えは同じでも計算時間が人数の2乗に比例します。