2110. Number of Smooth Descent Periods of a Stock 股票的平滑下降时间段数量

2110. Number of Smooth Descent Periods of a Stock

2110. 股票的平滑下降时间段数量

You are given an integer array prices representing the daily price history of a stock, where prices[i] is the stock price on the i^th day.
给你一个整数数组 prices ，表示某只股票的每日价格历史，其中 prices[i] 表示第 i^th 天的股票价格。
A smooth descent period of a stock consists of one or more contiguous days such that the price on each day is lower than the price on the preceding day by exactly 1. The first day of the period is exempted from this rule.
股票的“平滑下降时段”由一个或多个连续的交易日组成，要求除该时段的第一天外，每一天的价格均比前一天**恰好低 1 **。
Return the number of smooth descent periods.
返回平滑下降时段的总数。

Example 1: 示例 1：

Input: prices = [3,2,1,4]
Output: 7
Explanation: There are 7 smooth descent periods:
[3], [2], [1], [4], [3,2], [2,1], and [3,2,1]
Note that a period with one day is a smooth descent period by the definition.

Example 2: 示例 2：

Input: prices = [8,6,7,7]
Output: 4
Explanation: There are 4 smooth descent periods: [8], [6], [7], and [7]
Note that [8,6] is not a smooth descent period as 8 - 6 ≠ 1.

Example 3: 示例 3：

Input: prices = [1]
Output: 1
Explanation: There is 1 smooth descent period: [1]

Ways of solving a problem 解题思路

• 用 dp[i] 表示以第 i 天结尾时间段的数量
• 当 i == 0 时，有 dp[0] = 1
• 对于 i > 0，要求每天的价格恰好比前一天少 1 ，需要考虑 prices[i] 与 prices[i - 1] 之间的关系
  • prices[i] == prices[i - 1] - 1, dp[i] = dp[i − 1] + 1
  • prices[i] != prices[i - 1] - 1, dp[i] = 1

class Solution {
public:
    long long getDescentPeriods(vector<int>& prices) {
        int n = prices.size();
        long long res = 1;
        std::vector<int> dp(n, 1);

        for (int i = 1; i < n; ++i) {
            if (prices[i] == prices[i - 1] - 1) {
                dp[i] = dp[i - 1] + 1;
            } else {
                dp[i] = 1;
            }
            res += dp[i];
        }
        return res;
    }
};

dp[i] 仅依赖于 dp[i - 1]，我们无需显式维护 dp 数组。相反，可在递归过程中使用一个整数 prev 来追踪 dp[i−1]
更快的版本

class Solution {
public:
    long long getDescentPeriods(vector<int>& prices) {
        int n = prices.size();
        long long res = 1;
        int prev = 1;

        for (int i = 1; i < n; ++i) {
            if (prices[i] == prices[i - 1] - 1) {
                prev++;
            } else {
                prev = 1;
            }
            res += prev;
        }
        return res;
    }
};