Lua滑动窗口最大值：单调队列的队尾淘汰

local function winMax(t, k)
    local out = {}
    for i = 1, #t - k + 1 do
        local m = t[i]
        for j = i, i + k - 1 do     -- 每窗重扫，n乘k
            m = math.max(m, t[j])
        end
        out[#out + 1] = m
    end
    return out
end

local function winMax(t, k)
    local q, out = {}, {}
    for i = 1, #t do
        while #q > 0 and t[q[#q]] <= t[i] do
            table.remove(q)         -- 队尾淘汰不可能的最大值
        end
        q[#q + 1] = i
        if q[1] <= i - k then table.remove(q, 1) end   -- 出窗弹头
        if i >= k then out[#out + 1] = t[q[1]] end
    end
    return out
end
sendmsg(actor, 1, "窗口最大值 " .. #winMax(
    {4, 3, 5, 4, 3, 3, 6, 7}, 3))