苏州网上挂号_新开传奇网站sf123_广州seo排名优化服务_磁力宝

股票平滑下跌阶段的数目

题目描述

给定一个整数数组 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，则形成一个平滑下降的阶段。否则，新的阶段就开始。

2. 解题关键：

   • 遍历 prices 数组，对于每一项，检查它是否比前一项小 1。如果是，说明当前股价继续组成一个平滑下降阶段。如果不是，则当前阶段结束，开始新的阶段。
   • 通过统计每个连续下降子序列的长度来计算平滑下降阶段的数量。

3. 具体步骤：

   • 使用变量 cur 来记录当前平滑下降阶段的长度。
   • 使用 cnt 来累计所有平滑下降阶段的总数。
   • 当发现一个新的下降阶段时，重置 cur 为 1，并累加到 cnt。

4. 时间复杂度：

   • 由于我们只需要一次遍历 prices 数组，因此时间复杂度为 O(n)，其中 n 为数组 prices 的长度。

代码实现

from typing import Listclass 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  # 如果当前股价不符合条件，重置当前阶段长度为1cnt += cur  # 累加当前阶段的所有平滑下降子数组return cnt

解析

1. 变量初始化：

   • n：数组 prices 的长度。
   • cur：表示当前平滑下降阶段的长度（从1开始计数）。
   • cnt：用来累计所有的平滑下降阶段的数目。

2. 遍历股价数组：

   • if i > 0 and prices[i] == prices[i-1] - 1：当当前股价等于前一日股价减1时，说明当前处于一个平滑下降阶段，因此cur累加。
   • 否则，cur 被重置为 1，表示新的平滑下降阶段开始。

3. 结果累加：

   • 每当一个股价点被处理时，都会把当前的阶段长度（即cur）加到总数cnt中。

4. 返回结果：

   • 最终返回所有平滑下降阶段的总数 cnt。

时间复杂度分析

• 由于我们只进行了一次遍历 prices 数组，所以时间复杂度为 O(n)，其中 n 是数组 prices 的长度。
• 空间复杂度为 O(1)，因为只用了常数空间存储 cur 和 cnt。

总结

本题通过遍历股价数组，结合简单的条件判断，能够高效地计算出所有平滑下降阶段的数量。这个问题考察了对连续子序列的处理能力，尤其是如何利用状态变量来跟踪并累积符合条件的子序列数量。