You are given an integer array prices
representing the daily price history of a stock, where prices[i]
is the stock price on the ith
day.
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.
Return the number of smooth descent periods.
Example 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:
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:
Input: prices = [1] Output: 1 Explanation: There is 1 smooth descent period: [1]
Constraints:
1 <= prices.length <= 105
1 <= prices[i] <= 105
Solution: DP
Same as longest decreasing subarray.
dp[i] := length of longest smoothing subarray ends with nums[i].
dp[i] = dp[i – 1] + 1 if nums[i] + 1 = nums[i – 1] else 1
Time complexity: O(n)
Space complexity: O(n) -> O(1)
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
// Author: Huahua class Solution { public: long long getDescentPeriods(vector<int>& prices) { const int n = prices.size(); vector<long long> dp(n, 1); long long ans = 1; for (int i = 1; i < n; ++i) { if (prices[i] - prices[i - 1] == -1) dp[i] = dp[i - 1] + 1; ans += dp[i]; } return ans; } }; |
请尊重作者的劳动成果,转载请注明出处!花花保留对文章/视频的所有权利。
如果您喜欢这篇文章/视频,欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Be First to Comment