股票平滑下跌阶段的数目

记牢这一句:dp[i] 是以第 i 天为结尾的下降阶段个数。今天比昨天恰好少 1,就 dp[i] = dp[i-1] + 1;否则 dp[i] = 1。答案就是所有 dp 之和。下面从第 0 天开始,一天一天往右扫。

总览 · 9 天股价,dp 待填：这是我们要处理的 9 天股价,从左到右下标 0 到 8。右边这排面板要记每一天的 dp 值,也就是以那天结尾的下降阶段个数,现在都还是问号。我们的活儿就是从左往右扫一遍,一天一天把 dp 填出来,边填边把它们累加进答案。

第 0 天 · 起点,自己就是一个阶段：先看第 0 天,股价 5。它前面没有更早的一天可以接,所以它只能自己单独成一个下降阶段。这一步不用比较,直接定下来。

第 0 天结算 · dp[0] = 1：第 0 天定成 dp[0] = 1,把它记到右边面板。累计答案也从 0 加到 1。这一个 1 代表阶段 [5]。开局第一个战果拿下,继续往右走。

第 1 天比较 · 5 与 4 差 1：来到第 1 天,股价 4。看它和前一天:第 0 天是 5,5 减 4 正好等于 1,接得上!前一天那条绿色的下降段可以整段延长到今天。

第 1 天结算 · dp[1] = 2：于是 dp[1] = dp[0] + 1 = 2。这条绿色下降段现在长到 2 天。把 2 记进面板,累计答案从 1 加到 3。

第 2 天比较 · 4 与 3 差 1：来到第 2 天,股价 3。看它和前一天:第 1 天是 4,4 减 3 正好等于 1,接得上!前一天那条绿色的下降段可以整段延长到今天。

第 2 天结算 · dp[2] = 3：于是 dp[2] = dp[1] + 1 = 3。这条绿色下降段现在长到 3 天。把 3 记进面板,累计答案从 3 加到 6。

第 3 天比较 · 3 与 6 差 -3：来到第 3 天,股价 6。看它和前一天:第 2 天是 3,今天反而涨了,差是 -3,不是恰好少 1。接不上!前面那条下降段到此为止,今天只能自己重新起一段。

第 3 天结算 · dp[3] = 1：于是 dp[3] = 1,今天自己单独成一段,面板记上 1。累计答案从 6 加到 7。别小看这个 1,漏了它答案就少。

第 4 天比较 · 6 与 6 差 0：来到第 4 天,股价 6。看它和前一天:第 3 天是 6,两天持平,差是 0,不是恰好少 1。接不上!前面那条下降段到此为止,今天只能自己重新起一段。

第 4 天结算 · dp[4] = 1：于是 dp[4] = 1,今天自己单独成一段,面板记上 1。累计答案从 7 加到 8。别小看这个 1,漏了它答案就少。

第 5 天比较 · 6 与 9 差 -3：来到第 5 天,股价 9。看它和前一天:第 4 天是 6,今天反而涨了,差是 -3,不是恰好少 1。接不上!前面那条下降段到此为止,今天只能自己重新起一段。

第 5 天结算 · dp[5] = 1：于是 dp[5] = 1,今天自己单独成一段,面板记上 1。累计答案从 8 加到 9。别小看这个 1,漏了它答案就少。

第 6 天比较 · 9 与 8 差 1：来到第 6 天,股价 8。看它和前一天:第 5 天是 9,9 减 8 正好等于 1,接得上!前一天那条绿色的下降段可以整段延长到今天。

第 6 天结算 · dp[6] = 2：于是 dp[6] = dp[5] + 1 = 2。这条绿色下降段现在长到 2 天。把 2 记进面板,累计答案从 9 加到 11。

第 7 天比较 · 8 与 7 差 1：来到第 7 天,股价 7。看它和前一天:第 6 天是 8,8 减 7 正好等于 1,接得上!前一天那条绿色的下降段可以整段延长到今天。

第 7 天结算 · dp[7] = 3：于是 dp[7] = dp[6] + 1 = 3。这条绿色下降段现在长到 3 天。把 3 记进面板,累计答案从 11 加到 14。

第 8 天比较 · 7 与 2 差 5：来到第 8 天,股价 2。看它和前一天:第 7 天是 7,今天跌得太多,差是 5,不是恰好少 1。接不上!前面那条下降段到此为止,今天只能自己重新起一段。

第 8 天结算 · dp[8] = 1：于是 dp[8] = 1,今天自己单独成一段,面板记上 1。累计答案从 14 加到 15。别小看这个 1,漏了它答案就少。

回放 · dp 全部填好,求和得 15：九天全部扫完,dp 依次是 1 2 3 1 1 1 2 3 1。把它们从左到右加起来:1 加 2 加 3 加 1 加 1 加 1 加 2 加 3 加 1,正好是 15。这就是平滑下降阶段的总数。每一天的 dp,数的就是以那天结尾的阶段个数,全加起来自然不重不漏。

换个视角 · 按极大下降段分组也是 15：参考代码没有逐天记 dp,而是把股价切成一段段极大下降段:[5,4,3] 是一段长 3,[6] 长 1,[6] 长 1,[9,8,7] 长 3,[2] 长 1。一段长 cnt 的下降段,内部能选出的连续子段个数是 cnt 乘以 cnt 加 1 的整体,再除以 2。于是 6 加 1 加 1 加 6 加 1 = 15,和逐天 dp 求和完全一致。两种写法思路相同,复杂度都是线性。

边界想清:单天记 1、无一处恰好差 1 就是天数本身、一整段长 n 连降 1 贡献 n 乘以 n 加 1 的整体,再除以 2。

面试重点:dp 递推可压成 O(1) 空间、分组闭式 cnt 乘以 cnt 加 1 的整体,再除以 2、答案用 64 位防溢出。