2110. Number of Smooth Descent Periods of a Stock
Description
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
Solutions
Solution 1: Two Pointers
We define an answer variable ans
, initially set to $0$.
Next, we use two pointers $i$ and $j$, pointing to the first day of the current smooth decline phase and the day after the last day of this phase, respectively. Initially, $i = 0$, $j = 0$.
Iterate through the array prices
from left to right. For each position $i$, we move $j$ to the right until $j$ reaches the end of the array or $prices[j - 1] - prices[j] \neq 1$. At this point, $cnt = j - i$ is the length of the current smooth decline phase, and we add $\frac{(1 + cnt) \times cnt}{2}$ to the answer variable ans
. Then, we update $i$ to $j$ and continue the iteration.
After the iteration ends, return the answer variable ans
.
The time complexity is $O(n)$, where $n$ is the length of the array prices
. The space complexity is $O(1)$.
1 2 3 4 5 6 7 8 9 10 11 12 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
|
1 2 3 4 5 6 7 8 9 10 11 12 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
|