股票平滑下跌阶段的数目 图解题解
这道题到底在问什么
- 输入
- prices = [3,2,1,4]
- 输出
- 7
- 输入
- prices = [8,6,7,7]
- 输出
- 4
- 输入
- prices = [1]
- 输出
- 1
最优解：一步一步想明白
- 3记牢这一句:dp[i] 是以第 i 天为结尾的下降阶段个数。今天比昨天恰好少 1,就 dp[i] = dp[i-1] + 1;否则 dp[i] = 1。答案就是所有 dp 之和。下面从第 0 天开始,一天一天往右扫。
- 4这是我们要处理的 9 天股价,从左到右下标 0 到 8。右边这排面板要记每一天的 dp 值,也就是以那天结尾的下降阶段个数,现在都还是问号。我们的活儿就是从左往右扫一遍,一天一天把 dp 填出来,边填边把它们累加进答案。
- 5先看第 0 天,股价 5。它前面没有更早的一天可以接,所以它只能自己单独成一个下降阶段。这一步不用比较,直接定下来。
- 6第 0 天定成 dp[0] = 1,把它记到右边面板。累计答案也从 0 加到 1。这一个 1 代表阶段 [5]。开局第一个战果拿下,继续往右走。
- 7来到第 1 天,股价 4。看它和前一天:第 0 天是 5,5 减 4 正好等于 1,接得上!前一天那条绿色的下降段可以整段延长到今天。
- 8于是 dp[1] = dp[0] + 1 = 2。这条绿色下降段现在长到 2 天。把 2 记进面板,累计答案从 1 加到 3。
- 9来到第 2 天,股价 3。看它和前一天:第 1 天是 4,4 减 3 正好等于 1,接得上!前一天那条绿色的下降段可以整段延长到今天。
- 10于是 dp[2] = dp[1] + 1 = 3。这条绿色下降段现在长到 3 天。把 3 记进面板,累计答案从 3 加到 6。
- 11来到第 3 天,股价 6。看它和前一天:第 2 天是 3,今天反而涨了,差是 -3,不是恰好少 1。接不上!前面那条下降段到此为止,今天只能自己重新起一段。
- 12于是 dp[3] = 1,今天自己单独成一段,面板记上 1。累计答案从 6 加到 7。别小看这个 1,漏了它答案就少。
- 13来到第 4 天,股价 6。看它和前一天:第 3 天是 6,两天持平,差是 0,不是恰好少 1。接不上!前面那条下降段到此为止,今天只能自己重新起一段。
- 14于是 dp[4] = 1,今天自己单独成一段,面板记上 1。累计答案从 7 加到 8。别小看这个 1,漏了它答案就少。
- 15来到第 5 天,股价 9。看它和前一天:第 4 天是 6,今天反而涨了,差是 -3,不是恰好少 1。接不上!前面那条下降段到此为止,今天只能自己重新起一段。
- 16于是 dp[5] = 1,今天自己单独成一段,面板记上 1。累计答案从 8 加到 9。别小看这个 1,漏了它答案就少。
- 17来到第 6 天,股价 8。看它和前一天:第 5 天是 9,9 减 8 正好等于 1,接得上!前一天那条绿色的下降段可以整段延长到今天。
- 18于是 dp[6] = dp[5] + 1 = 2。这条绿色下降段现在长到 2 天。把 2 记进面板,累计答案从 9 加到 11。
- 19来到第 7 天,股价 7。看它和前一天:第 6 天是 8,8 减 7 正好等于 1,接得上!前一天那条绿色的下降段可以整段延长到今天。
- 20于是 dp[7] = dp[6] + 1 = 3。这条绿色下降段现在长到 3 天。把 3 记进面板,累计答案从 11 加到 14。
- 21来到第 8 天,股价 2。看它和前一天:第 7 天是 7,今天跌得太多,差是 5,不是恰好少 1。接不上!前面那条下降段到此为止,今天只能自己重新起一段。
- 22于是 dp[8] = 1,今天自己单独成一段,面板记上 1。累计答案从 14 加到 15。别小看这个 1,漏了它答案就少。
- 23九天全部扫完,dp 依次是 1 2 3 1 1 1 2 3 1。把它们从左到右加起来:1 加 2 加 3 加 1 加 1 加 1 加 2 加 3 加 1,正好是 15。这就是平滑下降阶段的总数。每一天的 dp,数的就是以那天结尾的阶段个数,全加起来自然不重不漏。
- 24参考代码没有逐天记 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 求和完全一致。两种写法思路相同,复杂度都是线性。
⚠️ 容易写错的地方
✗ 错：用 int 累加答案
✓ 对：C++ 用 long long、Java 用 long,乘法处提升到 64 位
天数可达十万,最坏是一整段长下降,子段个数约为 n 乘以 n 加 1 的整体,再除以 2,远超 32 位整型上限,会溢出成负数或错值
✗ 错：把持平也当成下降,判 prices[i-1] ≥ prices[i]
✓ 对：必须是恰好少 1,即差严格等于 1
两天股价相等时差是 0、跌 2 时差是 2,都不算平滑下降;题目要的是每天比前一天恰好少 1
✗ 错：漏算单独一天的阶段
✓ 对：每天自己都算一个阶段,dp 至少是 1
哪怕它接不上前一天,自己单独一天也是一个合法的平滑下降阶段,dp 归 1 而不是归 0
✗ 错：用 O(n 方) 枚举所有子数组再逐段验证
✓ 对：一次线性扫描即可
每段长 cnt 的贡献有闭式 cnt 乘以 cnt 加 1 的整体,再除以 2,或用 dp 递推一遍带过,没必要双重循环枚举
完整代码（Python / C++ / Java）
Python
from __future__ import annotations
from typing import *
from collections import *
from functools import *
from itertools import *
from math import *
from heapq import *
from bisect import *
class Solution:
def getDescentPeriods(self, prices: List[int]) -> int:
ans = 0
i, n = 0, len(prices)
while i < n:
j = i + 1
while j < n and prices[j - 1] - prices[j] == 1:
j += 1
cnt = j - i
ans += (1 + cnt) * cnt // 2
i = j
return ansC++
#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
class Solution {
public:
long long getDescentPeriods(vector<int>& prices) {
long long ans = 0;
int n = prices.size();
for (int i = 0, j = 0; i < n; i = j) {
j = i + 1;
while (j < n && prices[j - 1] - prices[j] == 1) {
++j;
}
int cnt = j - i;
ans += (1LL + cnt) * cnt / 2;
}
return ans;
}
};Java
import java.util.*;
class Solution {
public long getDescentPeriods(int[] prices) {
long ans = 0;
int n = prices.length;
for (int i = 0, j = 0; i < n; i = j) {
j = i + 1;
while (j < n && prices[j - 1] - prices[j] == 1) {
++j;
}
int cnt = j - i;
ans += (1L + cnt) * cnt / 2;
}
return ans;
}
}复杂度
时间
O(n)
n 是天数。无论逐天记 dp 还是分组求和,每天只被看常数次:分组法里内层 j 一路只往前走、绝不回头,i 直接跳到 j,合起来每天恰好被访问一次,整体随天数线性增长
空间
O(1)
分组法只用了几个下标和一个累加变量,不额外开数组;逐天 dp 也只需记住前一天的 dp,一个变量滚动即可。都是常数额外空间。动画里的 dp 面板只是为了讲解,真实代码不必存下整排 dp
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 股票平滑下跌阶段的数目 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
这题的核心思路是什么?+
设 dp[i] 为以第 i 天结尾的平滑下降阶段个数。若今天比昨天恰好少 1,dp[i] = dp[i-1] + 1,否则 dp[i] = 1,答案是所有 dp 之和。因为只依赖前一天,dp 可以压成一个滚动变量,空间 O(1)。等价地也能把股价切成极大下降段,每段长 cnt 贡献 cnt 乘以 cnt 加 1 的整体,再除以 2。
为什么一段长 cnt 的下降段贡献是 cnt 乘以 cnt 加 1 的整体,再除以 2?+
这段内部任意一个连续子段都是合法的平滑下降阶段。长 cnt 的序列里,连续子段的个数等于从中选一个左端点和一个右端点的方案数,也就是 1 加 2 一直加到 cnt,等于 cnt 乘以 cnt 加 1 的整体,再除以 2。换成 dp 视角,这段的 dp 值正好是 1 2 直到 cnt,求和一致。
为什么要特别小心整型溢出?+
天数最多十万,极端情况是一整段连降 1,此时答案约为 n 乘以 n 加 1 的整体,再除以 2,数量级到十的九次方以上,超过 32 位有符号整型的上限。所以 C plus plus 和 Java 必须用 64 位整型累加,并在乘法处用 1LL 或 1L 提升类型;Python 整数不受限,无需担心。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄声线把 股票平滑下跌阶段的数目 一步步讲透（全站 0 节语音精讲，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。