股票平滑下跌阶段的数目 图解题解

恰好少 1 的阶段，到底数的是什么

prices[i] 是第 i 天股价，平滑下降阶段指连续一段天数、每天都比前一天恰好少 1，单独一天也算。例子 [3,2,1,4]：单天的 4 个，连降的 [3,2]、[2,1]、[3,2,1] 共 3 个，共 7。『恰好少 1』卡得死：[8,6,7,7] 差 2、涨、持平都不算，只剩 4 个单天阶段。

十万天约五十亿个连续段，试得完吗

长度 n 的数组有 n(n+1)/2 个连续段，n 顶到十万约五十亿段；每段再逐天验差，总量到 O(n³)（大 O：数据翻倍时工作量跟着涨几倍的记法），跑不进时限。浪费在哪？验 [3,2,1] 时，[3,2] 和 [2,1] 早各验过，长段平滑与否全由短段定。

dp[i] 为什么定成以第 i 天结尾

把短段答案存住复用，就是动态规划（DP，这题存的是『以某天结尾的下降段有几个』，后一天在上面加）。状态（dp 每格记的事）：dp[i] = 以第 i 天结尾的平滑下降阶段个数。每个阶段有唯一结尾天，按结尾天分堆相加，谁也不会被数两次，答案就是所有 dp 之和。

转移（由前一格推出这一格的规则）看相邻差：prices[i-1] - prices[i] 恰好等于 1 时，昨天每个阶段拖到今天照样恰差 1，再加今天单独成段，dp[i] = dp[i-1] + 1；差不是 1——涨、持平、跌超 1 都一样——旧段全接不上，dp[i] = 1。第 0 天前面没人，dp[0] = 1。

参考代码没有 dp 数组，cnt 在数什么

参考代码按段结账：外层 i 站在段开头，内层 j 从 i+1 往右，prices[j-1] - prices[j] == 1 就继续，停下时得到最长连降段，长度 cnt = j - i。段内逐天 dp 依次是 1、2、…、cnt，求和正是等差数列 (1+cnt)*cnt//2，记进 ans，i 跳到 j 找下一段。

[3,2,1,4] 上 dp 一天天加到 7

第 0 天股价 3，前面没人，dp[0] = 1，累计 1。第 1 天股价 2，3 - 2 = 1 接得上，dp[1] = dp[0] + 1 = 2，累计 3。第 2 天股价 1，2 - 1 = 1 又接上，dp[2] = 3，累计 6。第 3 天股价 4，1 - 4 = -3，断了，dp[3] = 1，累计 7，题面也是 7。

再走 [8,6,7,7]：相邻差依次 2、-1、0，没有一处恰好是 1，四天各自 dp = 1，加起来正是 4。

答案存进 int，十万天为什么会炸

i 和 j 只往右走，每天被访问一次，时间 O(n)；额外空间只几个下标和累加变量，O(1)。出事在数值范围：十万天一路连降 1 只有一段，贡献 (1+100000)*100000//2 = 5000050000，超出 32 位整型上限 2147483647，C++ 用 long long、Java 用 long，乘法要在 64 位下做完再除以 2。

断段时 dp 要归 1 而不是 0，归 0 会漏掉单天成段的那 1 个，[1] 就该返回 1。全数组没一处相邻恰差 1，答案就是天数。

Python

from __future__ import annotations
from typing import *
from collections import *
from functools import *
from itertools import *
from math import *
from heapq import *
from bisect import *
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

C++

#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
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;
    }
};

Java

import java.util.*;
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;
    }
}