股票价格跨度

先想最直白的:对每天的价格,从今天往左回头数,只要左边的价 ≤ 今天就继续数,一碰到更大的就停。我们先体会一下这样为什么慢。

暴力 · 处理第 6 天(价 85)：以最后一天 85 为例。暴力做法要从它左边的 75 开始,一格一格往左看,这一步就可能扫很多格。

暴力 · 往左数：75 ≤ 85,算进去,接着看更左边的 60。每一个都要亲自比一次。

暴力 · 往左数：60 也 ≤ 85,继续。最坏情况下(价格一直递减再来个最大值),这要一路扫到最左边,单次就 O(n)。

瓶颈在「每天都从头回扫」。其实那些被矮价跨过的天,以后永远不会再单独用到——它们已经被某个更高的价「吃掉」了。这就引出单调栈。

关键想法:栈里从底到顶价格严格递减。新价来了,凡是 ≤ 它的栈顶都被它「盖住」——弹出,并把这些天的跨度加到自己头上(它们能数到的,我也能数到)。

开始 · 栈为空：上面一排是即将依次喂入的股价,下面是栈(存 价·跨度 对)。开始时栈是空的,逐天处理。

第 0 天 · 价 100：第一天 100,栈是空的,没人能往回数,跨度 = 1。把 100·1 压栈(价 100、跨度 1)。

第 1 天 · 价 80：80 来了。栈顶 100 > 80,挡住了,不能弹。所以往回只数到自己,跨度 = 1,压入 80·1。

第 2 天 · 价 60：60 来了。栈顶 80 > 60,挡住,不弹。跨度 = 1,压入 60·1。栈里价格从底到顶是 100,80,60,正好递减。

第 3 天 · 价 70 来了：70 来了,跨度先记作 1(自己)。看栈顶 60 ≤ 70——它被 70 盖住了,要弹出,并把它的跨度加过来。

第 3 天 · 弹出 60·1：弹出 60·1,把它的跨度 1 累加过来,现在 70 的跨度变 2。再看新栈顶 80。

第 3 天 · 栈顶 80 > 70：新栈顶 80 > 70,挡住了,停止弹出。跨度 = 2,压入 70·2。注意 70 把刚才那个 60「吃」进了自己的跨度里。

第 4 天 · 价 60：又来个 60。栈顶 70 > 60,挡住,不弹。跨度 = 1,压入 60·1。

第 5 天 · 价 75 来了：75 来了,跨度先记 1。栈顶 60 ≤ 75,被盖住,要弹。

第 5 天 · 弹出 60·1：弹出 60·1,跨度累加成 2。再看新栈顶 70 ≤ 75——也被盖住,而 70 自己跨度是 2(早把那个 60 吃了),弹它要一次把 2 加过来。

第 5 天 · 弹出 70·2：弹出 70·2,把它的跨度 2 加过来,现在 75 的跨度是 4。这一下就把「60、70、60」三天连同自己一起数清了——不用再回头逐格扫。

第 5 天 · 栈顶 80 > 75：新栈顶 80 > 75,挡住,停。跨度 = 4,压入 75·4。这正是题面里 75 那天的答案。

第 6 天 · 价 85 来了：最后一天 85,跨度先记 1。栈顶 75 ≤ 85,被盖住,要弹。

第 6 天 · 弹出 75·4：弹出 75·4,一次把 4 加过来,跨度变 5。再看新栈顶 80 ≤ 85,也被盖住,继续弹。

第 6 天 · 弹出 80·1：弹出 80·1,跨度累加到 6。再看新栈顶 100。

第 6 天 · 栈顶 100 > 85：新栈顶 100 > 85,终于挡住了,停。跨度 = 6,压入 85·6。除了第一天的 100,前面 6 天都 ≤ 85。

全部完成 · 跨度一览：把七天的跨度并排看:1,1,1,2,1,4,6,和题面完全一致。栈里最后只剩 100 和 85——它们是「还可能挡住未来」的两座高峰。

虽然某一次 next 可能弹很多个(像 85 弹了 2 个、75 弹了 2 个),但弹出去就再也不回来。一生只进出一次,把总功摊到每次调用就是常数。

雷区实演 · 误用「严格 <」：假设连续两天都是 50。若条件写成「栈顶 &lt; 当前价才弹」,第二天的 50 弹不动第一天的 50,跨度错成 1;正确用 ≤ 时会弹出,跨度应为 2。

边界三连：先想清楚递增(全弹)、递减(全不弹)、首次(必为 1)三种极端,代码就稳了。

面试追问：把「均摊 O(1)」和「为何存跨度」讲清楚,是这题面试的得分点。