2393. Count Strictly Increasing Subarrays π
Description
You are given an array nums
consisting of positive integers.
Return the number of subarrays of nums
that are in strictly increasing order.
A subarray is a contiguous part of an array.
Example 1:
Input: nums = [1,3,5,4,4,6] Output: 10 Explanation: The strictly increasing subarrays are the following: - Subarrays of length 1: [1], [3], [5], [4], [4], [6]. - Subarrays of length 2: [1,3], [3,5], [4,6]. - Subarrays of length 3: [1,3,5]. The total number of subarrays is 6 + 3 + 1 = 10.
Example 2:
Input: nums = [1,2,3,4,5] Output: 15 Explanation: Every subarray is strictly increasing. There are 15 possible subarrays that we can take.
Constraints:
1 <= nums.length <= 105
1 <= nums[i] <= 106
Solutions
Solution 1: Enumeration
We can enumerate the number of strictly increasing subarrays ending at each element and then sum them up.
We use a variable $\textit{cnt}$ to record the number of strictly increasing subarrays ending at the current element, initially $\textit{cnt} = 1$. Then we traverse the array starting from the second element. If the current element is greater than the previous element, then $\textit{cnt}$ can be incremented by $1$. Otherwise, $\textit{cnt}$ is reset to $1$. At this point, the number of strictly increasing subarrays ending at the current element is $\textit{cnt}$, and we add it to the answer.
After the traversal, return the answer.
The time complexity is $O(n)$, where $n$ is the length of the array. The space complexity is $O(1)$.
1 2 3 4 5 6 7 8 9 10 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
|
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 |
|
1 2 3 4 5 6 7 8 9 10 11 12 |
|