2110. 股票平滑下跌階段的數目

思路

只要找到每次遞減一的最長長度，
再一次計算這個長度當中有幾種組合，加入到答案當中即可。

假如現在陣列是 $[4,3,2,1]$，
長度為 4 的「平滑下滑階段」共有 1 個，$[4,3,2,1]$
長度為 3 的「平滑下滑階段」共有 2 個，$[4,3,2]$、$[3,2,1]$
長度為 2 的「平滑下滑階段」共有 3 個，$[4,3]$、$[3,2]$、$[2,1]$
長度為 1 的「平滑下滑階段」共有 4 個，$[4]$、$[3]$、$[2]$、$[1]$
總共有 $(4\times{3})/2$ 個「平滑下滑階段」。

程式碼

數學

class Solution {
public:
    long long getDescentPeriods(vector<int>& prices) {
        int n = prices.size();
        long long res = 0, len = 0;
        for(int i = 0; i < n; ++i) {
            ++len;
            if(i == n - 1 || prices[i] - 1 != prices[i + 1]) {
                res += len * (len + 1) / 2;
                len = 0;
            }
        }
        return res;
    }
};
/*
[n, n - 1, ... 1]
1 + 2 + 3 + ... + n = n + 1 * n / 2
*/

複雜度分析

• 時間複雜度：$O(n)$
• 空間複雜度：$O(1)$