严格递增的子数组个数
难度:
标签:
题目描述
代码结果
运行时间: 51 ms, 内存: 30.5 MB
/*
题目思路:
使用Java Streams来解决这个问题稍微复杂一些。我们可以使用IntStream来遍历数组并计算严格递增子数组的个数。
我们将会使用一些辅助函数来帮助计算。
*/
import java.util.stream.IntStream;
public class StrictlyIncreasingSubarraysStream {
public static int countIncreasing(int[] arr) {
int[] count = {0};
IntStream.range(1, arr.length).forEach(i -> {
if (arr[i] > arr[i - 1]) {
count[0] += i - count[0];
}
});
return count[0];
}
public static void main(String[] args) {
int[] arr = {1, 3, 5, 4, 7};
System.out.println(countIncreasing(arr)); // 输出3
}
}
解释
方法:
该题解采用了一种单遍扫描的方法来解决问题。首先,初始化last为无穷大(inf),结果res和左边界l为0。遍历数组时,还额外在数组末尾添加一个无穷小(-inf)元素以处理边界情况。在每次迭代中,检查当前元素n是否大于上一个元素last。如果不是(即 n <= last),这意味着当前元素不能和前一个元素形成递增关系,因此之前的递增子序列到这里结束。此时计算从l到i-1的递增子数组的数量,利用组合数公式 (i-l)*(i-l+1)//2 进行计算,并累加到结果res。然后,更新左边界l为当前下标i。最后将当前元素n更新为last,用于下一轮比较。这个方法有效地在一次遍历中计算了所有严格递增子数组的数量。
时间复杂度:
O(n)
空间复杂度:
O(1)
代码细节讲解
🦆
为什么在数组末尾添加一个无穷小(-inf)元素,这样做的目的是什么?
▷🦆
在计算递增子数组的数量时使用的公式 `(i-l)*(i-l+1)//2` 是如何得到的?请解释这个公式背后的数学原理。
▷🦆
循环中检查`n <= last`来决定是否结束当前递增子数组的逻辑,能否处理所有的边界情况,例如数组的开始和结束?
▷