难度: Medium
给你一个整数数组 prices ，表示一支股票的历史每日股价，其中 prices[i] 是这支股票第 i 天的价格。
一个 平滑下降的阶段 定义为：对于 连续一天或者多天 ，每日股价都比 前一日股价恰好少 1 ，这个阶段第一天的股价没有限制。
请你返回 平滑下降阶段 的数目。
示例 1：
输入：prices = [3,2,1,4] 输出：7 解释：总共有 7 个平滑下降阶段： [3], [2], [1], [4], [3,2], [2,1] 和 [3,2,1] 注意，仅一天按照定义也是平滑下降阶段。
示例 2：
输入：prices = [8,6,7,7] 输出：4 解释：总共有 4 个连续平滑下降阶段：[8], [6], [7] 和 [7] 由于 8 - 6 ≠ 1 ，所以 [8,6] 不是平滑下降阶段。
示例 3：
输入：prices = [1] 输出：1 解释：总共有 1 个平滑下降阶段：[1]
提示：
1 <= prices.length <= 1051 <= prices[i] <= 105运行时间: 92 ms
内存: 28.5 MB
class Solution:
def getDescentPeriods(self, prices: List[int]) -> int:
# 以O(N)的复杂度找到独立最大的平滑下降阶段
# 假设当前的独立最大平滑下降的左右端点分别是l,r
# ans +=（(r-l+1）+1)*(r-l+1)/2
n = len(prices)
ans = n
work = False
last = -1
l , r = 0 , 0
for i , ch in enumerate(prices):
if not work and last - ch == 1 :
work = True
l = i - 1
r = i
elif work and last - ch == 1 :
r = i
elif work and last - ch != 1 :
work = False
ans += (r-l+2)*(r-l+1)//2 - (r-l+1)
# print(l,r,ans)
last = ch
if work :
r = len(prices)-1
ans += (r-l+2)*(r-l+1)//2 - (r-l+1)
return ans
该题解使用了一个单次遍历的方法来统计所有的平滑下降阶段数。首先，初始化总阶段数为数组长度（考虑到每个元素自身也是一个阶段）。然后，使用变量work来标识是否处于一个平滑下降阶段中，last来存储上一个股价，以及l和r来标记当前下降阶段的起始和结束位置。遍历过程中，当检测到连续下降（即当前价格比前一个价格低1）时，更新r或开始一个新的阶段并记录l。当下降中断时，计算从l到r的下降阶段数，并加到总数中。最后，如果遍历结束时仍在一个下降阶段中，则对该阶段进行统计。这种方法确保了每个可能的下降子数组都被精确计数。
时间复杂度: O(n)
空间复杂度: O(1)
class Solution:
def getDescentPeriods(self, prices: List[int]) -> int:
n = len(prices)
ans = n # 初始化总阶段数为数组长度
work = False # 标志是否处于平滑下降阶段
last = -1 # 存储上一个价格，初始化为-1
l, r = 0, 0 # 初始化当前下降阶段的起始和结束位置
for i, ch in enumerate(prices):
if not work and last - ch == 1:
work = True # 开始一个新的平滑下降阶段
l = i - 1
r = i
elif work and last - ch == 1:
r = i # 继续当前的平滑下降阶段
elif work and last - ch != 1:
work = False # 平滑下降阶段结束
ans += (r-l+2)*(r-l+1)//2 - (r-l+1) # 计算当前阶段的总下降数并加到总数中
last = ch # 更新上一个价格
if work:
r = len(prices)-1 # 如果结尾仍然是下降阶段，处理这一段
ans += (r-l+2)*(r-l+1)//2 - (r-l+1)
return ans
在算法中，`ans` 初始化为数组长度 `n` 是因为题目要求计算所有可能的下降阶段数，包括长度为1的阶段。每个单独的元素被视为一个长度为1的下降阶段。因此，初始化 `ans` 为 `n` 直接计算了这些单元素阶段，后续的计算将专注于长度大于1的下降阶段。
`work` 是一个标志变量，用以指示当前是否处于一个平滑下降阶段。当 `work` 为 `false` 且检测到当前价格比上一个价格低1时，会将 `work` 设为 `true` 并记录下降阶段的开始位置 `l`。如果 `work` 已经是 `true`，则继续检测下降模式，更新结束位置 `r`。当价格不再满足下降条件时，将 `work` 设为 `false` 并计算该下降阶段的贡献，然后继续寻找下一个可能的下降阶段。这样，`work` 变量有效地管理了下降阶段的开始和结束，确保每个阶段被正确地识别和计算。
公式 `(r-l+2)*(r-l+1)//2 - (r-l+1)` 用于计算从位置 `l` 到 `r` 的下降阶段中所有可能的子数组数量。首先，`(r-l+2)*(r-l+1)//2` 是一个等差数列求和公式，计算从位置 `l` 到 `r` 这些连续元素可以形成的所有子数组数量。然而，因为子数组长度必须大于1，所以需要减去这些元素单独作为子数组的数量 `(r-l+1)`。结果就是长度大于1的所有下降子数组的数量。
如果在遍历结束时，`work` 标志仍然为 `true`，这表明最后一个元素还处于一个未结束的平滑下降阶段。在这种情况下，我们需要将结束位置 `r` 设为最后一个元素的索引，即 `prices.length-1`。然后，使用之前提到的公式 `(r-l+2)*(r-l+1)//2 - (r-l+1)` 来计算这一阶段的子数组数量，并将这个数量加到总答案 `ans` 中。这确保了所有的下降阶段，包括数组末尾的阶段，都被正确地计算和统计。