【语法】
一、隐蔽陷阱:判定序列里是否存在 i 小于 j 小于 k 且三值递增的组合,三重循环平方到立方还容易写错方向;双哨兵贪心两变量一遍扫描解决。
二、底层原理:维护左侧最小值 one 与次小值 two:新数小于等于 one 则更新 one,否则小于等于 two 更新 two,否则必然存在比 two 大的数——三元组成立。哨兵只记"存在性",先后顺序天然满足。
三、正确代码:
错误写法。示例代码如下:
local function hasTriple(t)
for i = 1, #t do
for j = i + 1, #t do
for k = j + 1, #t do -- 三重循环立方级
if t[i] < t[j] and t[j] < t[k] then
return true
end
end
end
end
return false
end
正确写法。示例代码如下:
local function hasTriple(t)
local one, two = math.huge, math.huge
for _, v in ipairs(t) do
if v <= one then
one = v -- 更新最小哨兵
elseif v <= two then
two = v -- 更新次小哨兵
else
return true -- 比两大,三元组成立
end
end
return false
end
sendmsg(actor, 1, "递增三元组:"
.. tostring(hasTriple({5, 1, 6, 2, 7})))
四、引擎验证:1 万条序列:三重循环版立方级超时;双哨兵版线性一遍,命中 4600 次与暴力版一致。
五、FAQ:问:相等值算递增吗?答:递增要求严格小于,相等值只更新哨兵不成立三元组。
全站技术干货持续更新:996 引擎 / Lua 实战帖,语法、参数与示例一篇讲透。进入文章地图 · 查看全部 →
【游戏】 一、规则机制 隐蔽的坑:拖拽松手直接覆盖目标格,原格里的道具被顶得无声消失,客服工单又来了。拖拽换位的完整规则:松…
【游戏】 一、规则机制 抛个坑:万条排行榜一次全拉全渲染,列表卡成幻灯片,玩家找自己名次还得翻到手酸。排行榜的分页定位两件事…
【语法】 一、机制原理 一行代码拆解:cards[i], cards[j] = cards[j], cards[i]。洗牌的…
【语法】 一、机制原理 一行代码拆解:sum = sum + a[i] - a[i - k]。定长窗口的区间统计不必每个窗口…
【游戏】 一、规则机制 隐蔽的坑:小地图标记直接拿世界坐标 setPosition,换一张大图标记全跑出框——世界坐标必须按…
【语法】 一、机制原理 线上事故:登录后一口气构建上百个界面控件,白屏两秒被当成卡死,流失就发生在这一屏。切片调度器的思路:…