【语法】
一、隐蔽陷阱
一个栈要支持随时取最小值:每次都遍历一遍是 O(n),数据量大时查询卡顿——辅助结构要加多少额外空间,两个栈能不能解决?
二、底层原理
双栈同步:辅助栈与主栈同高,压栈时压入新值与辅助栈顶的较小者,出栈两栈同步弹出。任意时刻辅助栈顶即全栈最小,压栈出栈取最小都是 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 data, mins = {}, {}
local function mpush(v)
data[#data + 1] = v
mins[#mins + 1] = math.min(v, mins[#mins] or v)
end
local function mpop()
mins[#mins] = nil
local v = data[#data]
data[#data] = nil
return v
end
local function getMin()
return mins[#mins]
end
mpush(4); mpush(2); mpush(6); mpop()
local p = getplayerbyname("min01")
sendmsg(p, 1, "最小 " .. getMin())
四、引擎验证
压 4、2、6 后弹出 6,取最小得 2;辅助栈与主栈同步,零遍历。
五、FAQ
问:空栈取最小呢?
答:调用侧先判空。
问:要同时取最大呢?
答:再加一条最大辅助栈。
全站技术干货持续更新:996 引擎 / Lua 实战帖,语法、参数与示例一篇讲透。进入文章地图 · 查看全部 →
【游戏】 一、业务场景 帮战阵亡后装备掉落,成员来不及捡回就被别人拿走。义庄上线:帮战阵亡装备自动送入帮会义庄暂存 24 小…
【游戏】 一、业务场景 帮会成员的首饰全靠系统掉落,样式千篇一律没有个性。金匠铺上线:帮会招募金匠,成员捐材料委托打造专属戒…
【游戏】 一、业务场景 帮会资金全靠成员自发捐献,收入不稳定。赋税制度上线:帮会驻地周边商户按周缴纳定额赋税,帮会统一收缴入…
【游戏】 一、业务场景 帮会押运任务单人跑容易被打劫,多人组队又怕分赃不均。镖客制度上线:押运任务可招募镖客护送,镖客保镖费…
【语法】 一、隐蔽陷阱 有序数组里找目标值的插入位置:逐个从头比对是 O(n),二分查找 O(log n) 但边界条件容易写…
【语法】 一、隐蔽陷阱 判断两个字符串是否同构(单射映射):只用一个映射表从 s 映到 t,漏了反向校验——多个 s 字符映…