给定一个由 正整数 组成的数组 nums
。
返回 严格递增 顺序的 nums
子数组 的数目。
子数组 是数组的一部分,且是 连续 的。
示例 1:
输入: nums = [1,3,5,4,4,6] 输出: 10 解释: 严格递增的子数组如下: - 长度为 1 的子数组: [1], [3], [5], [4], [4], [6]。 - 长度为 2 的子数组: [1,3], [3,5], [4,6]。 - 长度为 3 的子数组: [1,3,5]。 子数组的总数是 6 + 3 + 1 = 10。
示例 2:
输入: nums = [1,2,3,4,5] 输出: 15 解释: 每个子数组都严格递增。我们可以取 15 个子数组。
提示:
1 <= nums.length <= 105
1 <= nums[i] <= 106
方法一:双指针
利用双指针,找到每一段连续递增子数组的长度,我们记为 cnt
,每次将
时间复杂度
方法二:枚举
我们可以枚举数组中的每一个元素,找到以该元素为结尾的严格递增子数组的个数,然后将这些个数累加到答案中。
时间复杂度
class Solution:
def countSubarrays(self, nums: List[int]) -> int:
ans = i = 0
while i < len(nums):
j = i + 1
while j < len(nums) and nums[j] > nums[j - 1]:
j += 1
cnt = j - i
ans += (1 + cnt) * cnt // 2
i = j
return ans
class Solution:
def countSubarrays(self, nums: List[int]) -> int:
ans = pre = cnt = 0
for x in nums:
if pre < x:
cnt += 1
else:
cnt = 1
pre = x
ans += cnt
return ans
class Solution {
public long countSubarrays(int[] nums) {
long ans = 0;
int i = 0, n = nums.length;
while (i < n) {
int j = i + 1;
while (j < n && nums[j] > nums[j - 1]) {
++j;
}
long cnt = j - i;
ans += (1 + cnt) * cnt / 2;
i = j;
}
return ans;
}
}
class Solution {
public long countSubarrays(int[] nums) {
long ans = 0;
int pre = 0, cnt = 0;
for (int x : nums) {
if (pre < x) {
++cnt;
} else {
cnt = 1;
}
pre = x;
ans += cnt;
}
return ans;
}
}
class Solution {
public:
long long countSubarrays(vector<int>& nums) {
long long ans = 0;
int i = 0, n = nums.size();
while (i < n) {
int j = i + 1;
while (j < n && nums[j] > nums[j - 1]) {
++j;
}
int cnt = j - i;
ans += 1ll * (1 + cnt) * cnt / 2;
i = j;
}
return ans;
}
};
class Solution {
public:
long long countSubarrays(vector<int>& nums) {
long long ans = 0;
int pre = 0, cnt = 0;
for (int x : nums) {
if (pre < x) {
++cnt;
} else {
cnt = 1;
}
ans += cnt;
pre = x;
}
return ans;
}
};
func countSubarrays(nums []int) int64 {
ans := 0
i, n := 0, len(nums)
for i < n {
j := i + 1
for j < n && nums[j] > nums[j-1] {
j++
}
cnt := j - i
ans += (1 + cnt) * cnt / 2
i = j
}
return int64(ans)
}
func countSubarrays(nums []int) (ans int64) {
pre, cnt := 0, 0
for _, x := range nums {
if pre < x {
cnt++
} else {
cnt = 1
}
ans += int64(cnt)
pre = x
}
return
}
function countSubarrays(nums: number[]): number {
let ans = 0;
let i = 0;
const n = nums.length;
while (i < n) {
let j = i + 1;
while (j < n && nums[j] > nums[j - 1]) {
++j;
}
const cnt = j - i;
ans += ((1 + cnt) * cnt) / 2;
i = j;
}
return ans;
}
function countSubarrays(nums: number[]): number {
let ans = 0;
let pre = 0;
let cnt = 0;
for (const x of nums) {
if (pre < x) {
++cnt;
} else {
cnt = 1;
}
ans += cnt;
pre = x;
}
return ans;
}