【语法】
一、隐蔽陷阱
记录一串操作消耗,要随时报出历史最低值:每次重新扫描是 O(n),数据量大时查询卡顿;临时排序更是本末倒置——有没有每步 O(1) 的取最小方案?
二、底层原理
辅助同步栈:主栈正常进出;辅助栈在每入栈一个元素时同步压入"当前最小"(新值与辅助栈顶取小),出栈两栈同步弹出。任意时刻辅助栈顶即全栈最小,进出与查询全部 O(1),代价是多一倍存储。
三、正确代码
基础写法(普通栈):
local stack = {}
local function push(v)
stack[#stack + 1] = v
end
local function pop()
local v = stack[#stack]
stack[#stack] = nil
return v
end
进阶写法(最小栈三件套):
local mainS, minS = {}, {}
local function mpush(v)
mainS[#mainS + 1] = v
local cur = minS[#minS]
minS[#minS + 1] = (cur and cur < v) and cur or v
end
local function mpop()
minS[#minS] = nil
local v = mainS[#mainS]
mainS[#mainS] = nil
return v
end
local function getMin()
return minS[#minS]
end
mpush(5); mpush(3); mpush(8); mpop()
local p = getplayerbyname("stack01")
sendmsg(p, 1, "当前最小 " .. getMin())
四、引擎验证
压 5、3、8 后弹出 8,取最小得 3;连弹两次最小值依次为 3、5,全程零扫描。
五、FAQ
问:辅助栈会很大吗?
答:与主栈同长,每元素多存一个数。
问:还要取最大呢?
答:再加一条最大辅助栈,结构相同。
全站技术干货持续更新:996 引擎 / Lua 实战帖,语法、参数与示例一篇讲透。进入文章地图 · 查看全部 →
【游戏功能】 一、一次高帧率翻车 测试服反馈:火球术在 60 帧的旧机器上百发百中,换 144 帧电竞屏,弹道经常从目标身上…
【游戏】 一、规则机制 线上事故:玩家收藏了心水商品等降价,降价了却没人告诉,便宜被别人捡走,差评点名"收藏功能是摆设"。关…
【语法】 一、机制原理 抛坑提问:网格上"离目标还有多远",用直线距离还是走格数?三种距离各有地盘:曼哈顿距离是横差绝对值加…
【游戏】 一、规则机制 隐蔽的坑:求助入口埋在设置页第三层,玩家出问题第一反应是去群里骂,问题与账号信息对不上号。客服入口改…
【语法】 一、机制原理 一行代码拆解:r = (r + n / r) / 2。不靠数学库也算得出平方根:先随手猜一个值,真平…
【语法】 一、机制原理 一行代码拆解:h = (h 31 + byte) % m。想给字符串分桶、给缓存分片,需要一个把任意…