当前位置：首页 > article >正文

力扣2110股票平滑下跌阶段的数目

article 2025/1/5 6:06:08

股票平滑下跌阶段的数目

题目描述

给定一个整数数组 prices，其中 prices[i] 表示第 i 天的股价。一个平滑下降阶段定义为：对于连续的多天，每日股价都比前一日股价恰好少1。

平滑下降阶段的数目即为所有符合条件的连续子数组的个数。

示例

示例 1：

输入：

prices = [3, 2, 1, 4]

输出：

解释：
总共有 7 个平滑下降阶段：

[3]
[2]
[1]
[4]
[3, 2]
[2, 1]
[3, 2, 1]

示例 2：

输入：

prices = [8, 6, 7, 7]

输出：

解释：
总共有 4 个连续平滑下降阶段：

[8]
[6]
[7]
[7]

由于 8 - 6 != 1，因此 [8, 6] 不是平滑下降阶段。

示例 3：

输入：

prices = [1]

输出：

解释：
只有一个平滑下降阶段 [1]。

思路

定义平滑下降阶段：
- 对于任意两个连续天数的股价，如果当前股价等于前一天股价减去1，则形成一个平滑下降的阶段。否则，新的阶段就开始。
解题关键：
- 遍历 prices 数组，对于每一项，检查它是否比前一项小 1。如果是，说明当前股价继续组成一个平滑下降阶段。如果不是，则当前阶段结束，开始新的阶段。
- 通过统计每个连续下降子序列的长度来计算平滑下降阶段的数量。
具体步骤：
- 使用变量 cur 来记录当前平滑下降阶段的长度。
- 使用 cnt 来累计所有平滑下降阶段的总数。
- 当发现一个新的下降阶段时，重置 cur 为 1，并累加到 cnt。
时间复杂度：
- 由于我们只需要一次遍历 prices 数组，因此时间复杂度为 O(n)，其中 n 为数组 prices 的长度。

代码实现

from typing import List

class Solution:
    def getDescentPeriods(self, prices: List[int]) -> int:
        n = len(prices)  # 股票价格的天数
        cur, cnt = 0, 0  # cur用于记录当前平滑下降阶段的长度，cnt用于记录总的阶段数
        
        # 遍历每一天的股价
        for i in range(n):
            if i > 0 and prices[i] == prices[i-1] - 1:  # 如果当前股价比前一天低1，属于一个下降阶段
                cur += 1  # 当前阶段长度增加
            else:
                cur = 1  # 如果当前股价不符合条件，重置当前阶段长度为1
            cnt += cur  # 累加当前阶段的所有平滑下降子数组
        return cnt

解析

变量初始化：
- n：数组 prices 的长度。
- cur：表示当前平滑下降阶段的长度（从1开始计数）。
- cnt：用来累计所有的平滑下降阶段的数目。
遍历股价数组：
- if i > 0 and prices[i] == prices[i-1] - 1：当当前股价等于前一日股价减1时，说明当前处于一个平滑下降阶段，因此cur累加。
- 否则，cur 被重置为 1，表示新的平滑下降阶段开始。
结果累加：
- 每当一个股价点被处理时，都会把当前的阶段长度（即cur）加到总数cnt中。
返回结果：
- 最终返回所有平滑下降阶段的总数 cnt。