题目

给你一个整数数组 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 <= 10^5
• 1 <= prices[i] <= 10^5

解题思路

这道题的关键在于发现子数组数量与连续下降长度之间的数学规律。

假设我们找到了一段长度为 $L$ 的连续平滑下降区间，例如 [5, 4, 3]，长度为 3。

我们可以列举以最后一个数字 3 结尾的所有平滑下降阶段：

1. [3] (长度 1)

2. [4, 3] (长度 2)

3. [5, 4, 3] (长度 3)

结论：如果当前位置 $i$ 是一个连续平滑下降序列的第 $k$ 个元素，那么以该元素结尾的平滑下降阶段就有 $k$ 个。

2. 算法流程

我们可以遍历数组，维护一个变量 length，表示当前连续平滑下降的长度。

1. 初始化总数 ans = 1（第一个元素本身算 1 个），当前连续长度 length = 1。

2. 从数组的第 2 个元素开始遍历（下标 $i$ 从 1 到 $n-1$）：

   • 判断条件：如果 prices[i-1] - prices[i] == 1（即前一天比今天多 1，满足平滑下降）：

     • 说明当前的连续下降趋势还在延续，我们将 length 加 1。

   • 否则：

     • 连续中断了，以当前元素结尾的平滑下降阶段只有它自己，重置 length = 1。

   • 累加：将当前的 length 加入到结果 ans 中。

3. 返回 ans。

复杂度分析

• 时间复杂度：$O(N)$，其中 $N$ 是数组长度。我们只需要遍历一次数组。

• 空间复杂度：$O(1)$，只需要常数级别的变量来存储结果和当前长度。

具体代码

func getDescentPeriods(prices []int) int64 {

    ans := int64(0)
    cicle := int64(1)
    for i := 1; i < len(prices); i++ {
        if prices[i - 1] - prices[i] == 1 {
            cicle++
        } else {
            ans += ((cicle + 1) * cicle) / 2
            cicle = 1
        }
    }
    ans += ((cicle + 1) * cicle) / 2
    return ans
}