Question

2110. 股票平滑下跌阶段的数目

English Version

题目描述

给你一个整数数组 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

解法

方法一：双指针

我们定义一个答案变量 ans，初始值为 $0$。

接下来，我们使用双指针 $i$ 和 $j$，分别指向当前平滑下降阶段的第一天和最后一天的下一天。初始时 $i = 0$, $j = 0$。

从左到右遍历数组 prices，对于每个位置 $i$，我们将 $j$ 向右移动，直到 $j$ 到达数组末尾或者 $prices[j - 1] - prices[j] \neq 1$ 为止。此时，$cnt = j - i$ 即为当前平滑下降阶段的长度，我们累加 $\frac{(1 + cnt) \times cnt}{2}$ 到答案变量 ans 中。接下来将 $i$ 更新为 $j$，继续遍历。

遍历结束后，返回答案变量 ans 即可。

时间复杂度 $O(n)$，空间复杂度 $O(1)$。其中 $n$ 为数组 prices 的长度。

class Solution:
  def getDescentPeriods(self, prices: List[int]) -> int:
    ans = 0
    i, n = 0, len(prices)
    while i < n:
      j = i + 1
      while j < n and prices[j - 1] - prices[j] == 1:
        j += 1
      cnt = j - i
      ans += (1 + cnt) * cnt // 2
      i = j
    return ans

class Solution {
  public long getDescentPeriods(int[] prices) {
    long ans = 0;
    int n = prices.length;
    for (int i = 0, j = 0; i < n; i = j) {
      j = i + 1;
      while (j < n && prices[j - 1] - prices[j] == 1) {
        ++j;
      }
      int cnt = j - i;
      ans += (1L + cnt) * cnt / 2;
    }
    return ans;
  }
}

class Solution {
public:
  long long getDescentPeriods(vector<int>& prices) {
    long long ans = 0;
    int n = prices.size();
    for (int i = 0, j = 0; i < n; i = j) {
      j = i + 1;
      while (j < n && prices[j - 1] - prices[j] == 1) {
        ++j;
      }
      int cnt = j - i;
      ans += (1LL + cnt) * cnt / 2;
    }
    return ans;
  }
};

func getDescentPeriods(prices []int) (ans int64) {
  n := len(prices)
  for i, j := 0, 0; i < n; i = j {
    j = i + 1
    for j < n && prices[j-1]-prices[j] == 1 {
      j++
    }
    cnt := j - i
    ans += int64((1 + cnt) * cnt / 2)
  }
  return
}

function getDescentPeriods(prices: number[]): number {
  let ans = 0;
  const n = prices.length;
  for (let i = 0, j = 0; i < n; i = j) {
    j = i + 1;
    while (j < n && prices[j - 1] - prices[j] === 1) {
      ++j;
    }
    const cnt = j - i;
    ans += Math.floor(((1 + cnt) * cnt) / 2);
  }
  return ans;
}