leetcode
leetcode 1851 ~ 1900
股票平滑下跌阶段的数目

股票平滑下跌阶段的数目

难度:

标签:

题目描述

代码结果

运行时间: 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`?请解释这样做的原因。
在算法中,`ans` 初始化为数组长度 `n` 是因为题目要求计算所有可能的下降阶段数,包括长度为1的阶段。每个单独的元素被视为一个长度为1的下降阶段。因此,初始化 `ans` 为 `n` 直接计算了这些单元素阶段,后续的计算将专注于长度大于1的下降阶段。
🦆
算法使用了变量`work`来标识是否处于平滑下降阶段,能否详细解释`work`的状态转换过程及其在算法中的作用?
`work` 是一个标志变量,用以指示当前是否处于一个平滑下降阶段。当 `work` 为 `false` 且检测到当前价格比上一个价格低1时,会将 `work` 设为 `true` 并记录下降阶段的开始位置 `l`。如果 `work` 已经是 `true`,则继续检测下降模式,更新结束位置 `r`。当价格不再满足下降条件时,将 `work` 设为 `false` 并计算该下降阶段的贡献,然后继续寻找下一个可能的下降阶段。这样,`work` 变量有效地管理了下降阶段的开始和结束,确保每个阶段被正确地识别和计算。
🦆
在处理平滑下降阶段结束时,公式`(r-l+2)*(r-l+1)//2 - (r-l+1)`用于计算什么?请解释这个公式的具体含义及计算逻辑。
公式 `(r-l+2)*(r-l+1)//2 - (r-l+1)` 用于计算从位置 `l` 到 `r` 的下降阶段中所有可能的子数组数量。首先,`(r-l+2)*(r-l+1)//2` 是一个等差数列求和公式,计算从位置 `l` 到 `r` 这些连续元素可以形成的所有子数组数量。然而,因为子数组长度必须大于1,所以需要减去这些元素单独作为子数组的数量 `(r-l+1)`。结果就是长度大于1的所有下降子数组的数量。
🦆
如何处理最后一个元素仍然处于平滑下降阶段的情况?请详细描述这种情况下的处理逻辑。
如果在遍历结束时,`work` 标志仍然为 `true`,这表明最后一个元素还处于一个未结束的平滑下降阶段。在这种情况下,我们需要将结束位置 `r` 设为最后一个元素的索引,即 `prices.length-1`。然后,使用之前提到的公式 `(r-l+2)*(r-l+1)//2 - (r-l+1)` 来计算这一阶段的子数组数量,并将这个数量加到总答案 `ans` 中。这确保了所有的下降阶段,包括数组末尾的阶段,都被正确地计算和统计。

相关问题