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

每个平滑下降的阶段为一个段,先计算有几个段以及每个段有几个数

如果段中有1个数,则ret += 1

否则 ret += 段的长度  (段中每个数单独一个段),然后ret += 这个段中任意长度的相邻数段的数量 (这个就等于C(2,m),其中m为段的长度)

class Solution {
public:
    vector<int> v;
    long long getDescentPeriods(vector<int>& prices) {
        if(prices.size() == 1) return 1;
        int len = prices.size();
        int cnt = 1;
        for(int i = 0; i < len - 1; i++)
        {
            if(prices[i + 1] - prices[i] == -1)
                cnt++;
            else
            {
                v.push_back(cnt);
                cnt = 1;
            }
            if(i == len - 2) v.push_back(cnt);
        }
        // if(prices[len - 1] - prices[len - 2] != -1)
        //     v.push_back(1);
        long long ret = 0;
        for(int i = 0; i < v.size(); i++)
        {
            if(v[i] == 1) ret += 1;
            else
            {
                ret += v[i];
                ret += (long long)v[i] * (v[i] - 1) / 2;
            }
        }
        return ret;

        
    }
};

 

上一篇:通过先序和中序数组生成后序数组(Java)


下一篇:Codeforces Round #738 (Div. 2) 题解