Your second example gets the first $n, not the last. Both are pretty wasteful of resources. Here's one way to do it,

{
    local $_;
    while (<FILEHANDLE>) {
        push @lines, $_ if /criteria/;
        shift @lines if @lines > $n;
    }
}
[download]

I've localized $_ since while (<>) {...} does not, but that is usually not necessary.