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 <= 1051 <= 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 cnt to record the number of strictly increasing subarrays ending at the current element, initially cnt = 1. Then we traverse the array starting from the second element. If the current element is greater than the previous element, then cnt can be incremented by 1. Otherwise, cnt is reset to 1. At this point, the number of strictly increasing subarrays ending at the current element is 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).
class Solution: def countSubarrays(self, nums: List[int]) -> int: ans = cnt = 1 for x, y in pairwise(nums): if x < y: cnt += 1 else: cnt = 1 ans += cnt return ans(code-box)
