Raku: 解 Leader Elements (PWC Week 78)

發佈於:

Leader Elements 是 Perl Weekly Challenge 078 番裡的一題。

題目全文如下:


You are given an array @A containing distinct integers. Write a script to find all leader elements in the array @A. Print (0) if none found. An element is leader if it is greater than all the elements to its right side.

Example 1:

Input: @A = (9, 10, 7, 5, 6, 1)
Output: (10, 7, 6, 1)

Example 2:

Input: @A = (3, 4, 5)
Output: (5)

依定義,「Leader Element」就是「比其後方都大」的元素。不過依題目範例的話,最後一個元素必定是 Leader Element。感覺起來有點怪怪的,不過就依這兩條規則來玩吧。

我所想到的直觀解法,是從 @A 後方向前逐一迭代,記下「目前看到的最大值」。如果目前元素比目前最大值更大,那就表示目前元素比其後方所有值都大,即為 Leader Element。

依此想法所做出的函式如下:

sub leaders(@A) {
    my $max = -Inf;
    return @A.reverse.grep(-> $v { ($v > $max) ?? ( $max = $v ; True ) !! False }).reverse();
}

核心部份 grep 主作用是決定目前值 $v 是否為 Leader Element ($v > $max),副作用是更新 $max。Raku 有 Inf(無限大)與 -Inf(無限小) 可用,做為初始值十分方便。

這一題算是個有趣小品吧。