股票平滑下跌阶段的数目
难度:
标签:
题目描述
代码结果
运行时间: 92 ms, 内存: 28.5 MB
/*
* 思路:
* 1. 使用 Java Stream 解决该问题需要先将原始数组转换成包含前后元素比较结果的布尔数组。
* 2. 然后通过 reduce 操作累计平滑下降阶段的长度和计数。
*/
import java.util.stream.IntStream;
public class SmoothDescendingStagesStream {
public int countSmoothDescendingStages(int[] prices) {
int[] descLengths = new int[prices.length];
descLengths[0] = 1;
IntStream.range(1, prices.length).forEach(i -> {
descLengths[i] = (prices[i] == prices[i - 1] - 1) ? descLengths[i - 1] + 1 : 1;
});
return IntStream.of(descLengths).sum();
}
public static void main(String[] args) {
SmoothDescendingStagesStream sds = new SmoothDescendingStagesStream();
int[] prices = {3, 2, 1, 4};
System.out.println(sds.countSmoothDescendingStages(prices)); // 输出 7
}
}
解释
方法:
该题解使用了一个单次遍历的方法来统计所有的平滑下降阶段数。首先,初始化总阶段数为数组长度(考虑到每个元素自身也是一个阶段)。然后,使用变量work来标识是否处于一个平滑下降阶段中,last来存储上一个股价,以及l和r来标记当前下降阶段的起始和结束位置。遍历过程中,当检测到连续下降(即当前价格比前一个价格低1)时,更新r或开始一个新的阶段并记录l。当下降中断时,计算从l到r的下降阶段数,并加到总数中。最后,如果遍历结束时仍在一个下降阶段中,则对该阶段进行统计。这种方法确保了每个可能的下降子数组都被精确计数。
时间复杂度:
O(n)
空间复杂度:
O(1)
代码细节讲解
🦆
在算法中,为什么初始化`ans`为数组长度`n`?请解释这样做的原因。
▷🦆
算法使用了变量`work`来标识是否处于平滑下降阶段,能否详细解释`work`的状态转换过程及其在算法中的作用?
▷🦆
在处理平滑下降阶段结束时,公式`(r-l+2)*(r-l+1)//2 - (r-l+1)`用于计算什么?请解释这个公式的具体含义及计算逻辑。
▷🦆
如何处理最后一个元素仍然处于平滑下降阶段的情况?请详细描述这种情况下的处理逻辑。
▷