Medium

题目描述

给你一个整数数组 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] 不是平滑下降阶段，因为 8 - 6 ≠ 1。

示例 3：

输入：prices = [1]
输出：1
解释：有 1 个平滑下降阶段：[1]

提示：

  • 1 <= prices.length <= 10^5
  • 1 <= prices[i] <= 10^5

解题思路

这道题需要找到所有的平滑下降子数组的个数。平滑下降是指每一天的价格都比前一天恰好少1。

核心思路：

  1. 任何数组都可以分解为若干个相邻的最长平滑下降段。例如 [5,3,2,1,7,6] 可以分解为 [5] + [3,2,1] + [7,6]
  2. 对于长度为k的平滑下降段，它包含的子数组个数为 1+2+3+…+k = k*(k+1)/2
  3. 使用双指针或滑动窗口方法找到每个最长的平滑下降段

解法分析：

  • 方法一（推荐）： 双指针法，找到每个最长平滑下降段，计算其贡献
  • 方法二： 动态规划，逐步计算以每个位置结尾的平滑下降段长度

以第一种方法为例，我们用左右指针维护当前的平滑下降段，当不满足条件时，计算当前段的贡献并移动左指针。

时间复杂度： O(n)，每个元素最多被访问两次 空间复杂度： O(1)，只使用常数额外空间

代码实现

class Solution {
public:
    long long getDescentPeriods(vector<int>& prices) {
        int n = prices.size();
        long long result = 0;
        int left = 0;
        
        for (int right = 0; right < n; right++) {
            // 如果不满足平滑下降条件，更新左边界
            if (right > 0 && prices[right-1] - prices[right] != 1) {
                left = right;
            }
            // 当前段长度为 right - left + 1
            // 贡献的子数组个数为 right - left + 1
            result += right - left + 1;
        }
        
        return result;
    }
};

class Solution:
    def getDescentPeriods(self, prices: List[int]) -> int:
        n = len(prices)
        result = 0
        left = 0
        
        for right in range(n):
            # 如果不满足平滑下降条件，更新左边界
            if right > 0 and prices[right-1] - prices[right] != 1:
                left = right
            # 当前段长度为 right - left + 1
            # 贡献的子数组个数为 right - left + 1
            result += right - left + 1
        
        return result

public class Solution {
    public long GetDescentPeriods(int[] prices) {
        int n = prices.Length;
        long result = 0;
        int left = 0;
        
        for (int right = 0; right < n; right++) {
            // 如果不满足平滑下降条件，更新左边界
            if (right > 0 && prices[right-1] - prices[right] != 1) {
                left = right;
            }
            // 当前段长度为 right - left + 1
            // 贡献的子数组个数为 right - left + 1
            result += right - left + 1;
        }
        
        return result;
    }
}

var getDescentPeriods = function(prices) {
    const n = prices.length;
    let result = 0;
    let left = 0;
    
    for (let right = 0; right < n; right++) {
        // 如果不满足平滑下降条件，更新左边界
        if (right > 0 && prices[right-1] - prices[right] !== 1) {
            left = right;
        }
        // 当前段长度为 right - left + 1
        // 贡献的子数组个数为 right - left + 1
        result += right - left + 1;
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型分析
时间复杂度O(n) - 只需遍历数组一次，每个元素最多被访问常数次
空间复杂度O(1) - 只使用了常数个额外变量

相关题目