LeetCode 2110.股票平滑下跌阶段的数目：数学（一次遍历）

【LetMeFly】2110.股票平滑下跌阶段的数目：数学（一次遍历）

力扣题目链接：https://leetcode.cn/problems/number-of-smooth-descent-periods-of-a-stock/

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

解题方法：遍历

假设有3 33个连续下滑天[ 3 , 2 , 1 ] [3, 2, 1][3,2,1]，那么可以有3 , 2 , 1 3, 2, 13,2,1（连续3天共1种）、3 , 2 3, 23,2、2 , 1 2, 12,1（连续2天共2种）、3 33、2 22、1 11（连续1天共3种）这共计1 + 2 + 3 = 3 ( 3 + 1 ) 2 = 6 1+2+3=\frac{3(3+1)}{2}=61+2+3=23(3+1)​=6种平滑下降阶段。

同样的，n nn个连续下滑天就有n ( n + 1 ) 2 \frac{n(n+1)}22n(n+1)​种平滑下降阶段。

因此，我们只需要遍历一遍，看下原始数组中有多少连续下滑天，并将每个连续下滑天的平滑下降阶段种类数求和即可。

具体做法

具体而言，可以使用两个变量：l a s t lastlast和c n t cntcnt分别记录上一天的价格和当前连续下滑天，遇到连续下滑天中断的情况就计算一次a n s ansans，最后返回前也计算一次a n s ansans。

时空复杂度

• 时间复杂度O ( l e n ( p r i c e s ) ) O(len(prices))O(len(prices))
• 空间复杂度O ( 1 ) O(1)O(1)

AC代码

C++

/* * @LastEditTime: 2025-12-15 18:52:23 */typedeflonglongll;classSolution{public:llgetDescentPeriods(vector<int>&prices){ll ans=0,cnt=0;intlast=0;for(intt:prices){if(t!=last-1){ans+=cnt*(cnt+1)/2;// printf("t = %d, cnt = %lld\n", t, cnt);cnt=0;}last=t;cnt++;}returnans+cnt*(cnt+1)/2;}};

Python

''' LastEditTime: 2025-12-15 18:54:39 '''fromtypingimportListclassSolution:defgetDescentPeriods(self,prices:List[int])->int:ans=last=cnt=0forpinprices:ifp!=last-1:ans+=cnt*(cnt+1)//2cnt=0cnt+=1last=preturnans+cnt*(cnt+1)//2

Java

/* * @LastEditTime: 2025-12-15 21:37:22 */classSolution{publiclonggetDescentPeriods(int[]prices){longans=0,cnt=0;for(intlast=0,i=0;i<=prices.length;i++){if(i==prices.length||prices[i]!=last-1){ans+=cnt*(cnt+1)/2;cnt=0;}cnt++;if(i<prices.length){last=prices[i];}}returnans;}}

Go

/* * @LastEditTime: 2025-12-15 21:35:08 */packagemainfuncgetDescentPeriods(prices[]int)(ansint64){varcntint64last:=0fori:=0;i<=len(prices);i++{ifi==len(prices)||prices[i]!=last-1{ans+=cnt*(cnt+1)/2cnt=0}cnt++ifi<len(prices){last=prices[i]}}return}

Rust

/* * @LastEditTime: 2025-12-15 21:41:17 */implSolution{pubfnget_descent_periods(prices:Vec<i32>)->i64{letmutans:i64=0;letmutcnt:i64=0;letmutlast:i32=0;forpinprices{// 一借不还ifp!=last-1{ans+=cnt*(cnt+1)/2;cnt=0;}cnt+=1;last=p;}ans+cnt*(cnt+1)/2}}

End

今天跌得可不轻啊

同步发文于CSDN和我的个人博客，原创不易，转载经作者同意后请附上原文链接哦~

千篇源码题解已开源