class Solution {
public:
long long countSubarrays(vector<int>& nums) {
}
};
2393. 严格递增的子数组个数
给定一个由 正整数 组成的数组 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 <= 1051 <= nums[i] <= 106原站题解
cpp 解法, 执行用时: 128 ms, 内存消耗: 74.4 MB, 提交时间: 2023-10-16 23:25:09
class Solution {
public:
long long countSubarrays(vector<int>& nums) {
long long ans = 0;
int idxPre = -1, numPre = INT_MIN;
for (int i = 0; i < nums.size(); ++i) {
if (nums[i] <= numPre) {
idxPre = i - 1;
}
ans += i - idxPre;
//ans 每次加上以第i个数为结尾的严格递增子数列的个数
numPre = nums[i];
}
return ans;
}
};
java 解法, 执行用时: 3 ms, 内存消耗: 54.8 MB, 提交时间: 2023-10-16 23:24:47
class Solution {
public long countSubarrays(int[] nums) {
int length=nums.length;
int[]dp=new int[length];
dp[0]=1;
for(int i=1;i<length;i++){
if(nums[i]>nums[i-1]){
dp[i]=1+dp[i-1];
}else{
dp[i]=1;
}
}
long sum=0;
for(int i=0;i<length;i++){
sum+=dp[i];
}
return sum;
}
}
python3 解法, 执行用时: 684 ms, 内存消耗: 30.3 MB, 提交时间: 2023-10-16 23:24:27
class Solution:
def countSubarrays(self, nums: List[int]) -> int:
count = 1
pre = 1
for i in range(1, len(nums)):
if nums[i] > nums[i - 1]:
pre += 1
else:
pre = 1
count += pre
return count
golang 解法, 执行用时: 112 ms, 内存消耗: 8.6 MB, 提交时间: 2023-10-16 23:24:11
func countSubarrays(nums []int) int64 {
var ans int64
count := 1
for i := 1; i < len(nums); i++ {
if nums[i] <= nums[i-1] {
ans += int64(count * (count + 1) / 2)
count = 1
}else {
count++
}
}
ans += int64(count * (count + 1) / 2)
return ans
}