面试官:线上突然大量报错,你先查什么? 我:先查今天谁发了版
面试官问,线上突然一堆报错,你先查什么?
这看到看,今天谁发版了。
别笑,这玩意儿在公司里基本属于条件反射。系统平时装得跟老黄牛似的,突然原地抽风,十有八九不是“年久失修”,就是有人刚动过它。
评论区也挺真实。有人说,先看最近变更,别一上来就装高手满世界抓鬼。还有人更直接,说查发版记录这一步,能省掉一半无效加班。这个我信,太信了。
很多面试题就爱搞得好像自己在考福尔摩斯,非要你背一套排查八股:先看日志,再看链路,再看机器,再看数据库。流程当然没错,但真到线上冒烟那一刻,老油条都知道,先找“刚干过这事的人”最省命。
程序员干久了就懂,报错不可怕,最怕大家一脸无辜地说:我这边没动过。听到这句,眼皮都得跳一下。
算法题:柱状图中最大的矩形
这题看着像数组,真下手的时候,很多人第一反应却是双重循环:以每一根柱子当高度,往两边扩,看看最多能撑多宽。代码能写,样例也能过,一上数据量就开始喘。
问题不在“矩形”,在“边界”。 每根柱子真正关心的,不是自己有多高,而是它左边第一个比它矮的是谁,右边第一个比它矮的是谁。边界一旦定了,这根柱子能撑出来的最大面积就定了。
拿 heights = [2,1,5,6,2,3] 来说,5 和 6 这两根柱子看着就不太对劲,明显是能撑出大矩形的。比如高度 5,往左被 1 卡住,往右被 2 卡住,中间宽度是 2,面积就是 10。答案也正是它。
这种题我一般不想一根一根往两边扫,太笨。直接上单调栈,栈里存下标,保持对应高度单调递增。 一旦当前柱子比栈顶矮,说明栈顶那根柱子的“右边界”终于出现了,这时候就可以结算面积。
deflargestRectangleArea(heights):
stack = []
ans = 0
arr = [0] + heights + [0] # 两边补 0,少写很多边界判断
for i, h in enumerate(arr):
while stack and arr[stack[-1]] > h:
cur = stack.pop()
left = stack[-1] # 左边第一个更矮的位置
width = i - left - 1
ans = max(ans, arr[cur] * width)
stack.append(i)
return ans
这段代码真正值钱的地方,不是“用了栈”,而是 pop 的那一刻把三件事一次性拿全了:
当前下标 i,就是右边第一个更矮的柱子弹出后的栈顶 stack[-1],就是左边第一个更矮的柱子中间那段宽度,自然就是 i - left - 1
有些人写这题会专门开两个数组,分别存 left 和 right,也能做,但我第一眼通常不太想那样写。不是不行,是现场手写容易散,变量一多,边界就开始乱。
再看一个容易错的地方: 栈里为什么要维护“递增”,而且判断条件为什么是 >?
因为我们希望一旦出现更矮的柱子,就把前面比它高的全部清掉,让那些柱子在这一刻完成结算。至于相等高度怎么处理,> 还是 >= 都能做,但对应的边界定义要统一,不然宽度会算重。这种细节,面试里最容易栽。
最后说一句,这题表面在算面积,骨子里还是“找每个元素左右两侧第一个更小值”。 这种味道一旦闻出来,单调栈基本就跑不掉了。