leetcode
leetcode 2101 ~ 2150
严格递增的子数组个数

严格递增的子数组个数

难度:

标签:

题目描述

代码结果

运行时间: 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)元素,这样做的目的是什么?
在数组末尾添加一个无穷小(-inf)元素主要是为了处理数组结束时的边界情况。在算法中,我们需要在发现当前元素不大于前一个元素时计算递增子数组的数量。如果不添加这个-∞元素,那么在数组正常结束后,我们需要额外的逻辑来处理最后一个递增子数组的计算,因为最后一段递增子数组不会因为一个较小的元素而被终止。通过添加-∞,可以保证这个逻辑也适用于数组的最后一个元素,使得代码更加简洁和统一。
🦆
在计算递增子数组的数量时使用的公式 `(i-l)*(i-l+1)//2` 是如何得到的?请解释这个公式背后的数学原理。
这个公式是基于组合数学中的计数原理得到的。考虑从位置`l`到`i-1`的严格递增子数组,元素个数为`i-l`。如果我们要计算所有可能的连续子数组数量,则这相当于从这些元素中选择两个不同位置作为子数组的起始和结束点,还可以选择相同的位置,表示只包含一个元素的子数组。这样的选择方式总数为组合公式`C(n+1, 2)`,其中`n`是子数组长度。由组合数公式`C(n, k) = n! / [k!(n-k)!]`,我们可以得出`C(n+1, 2) = (n+1)*n/2`。这里的`n`相当于`i-l`,所以公式变为`(i-l)*(i-l+1)//2`。
🦆
循环中检查`n <= last`来决定是否结束当前递增子数组的逻辑,能否处理所有的边界情况,例如数组的开始和结束?
这种逻辑可以有效处理数组的开始和结束的边界情况。对于数组的开始,由于`last`初值设为无穷大,任何数组中的第一个元素都不会大于`last`,因此算法可以从第一个正常的递增子数组开始计算。对于数组的结束,通过在数组末尾添加一个无穷小(-inf)元素,可以确保最后一个递增子数组被正确计算。这是因为这个-∞元素肯定不大于前一个元素,从而触发计算最后一段递增子数组的逻辑。因此,这个检查机制可以在遍历中自然地处理所有边界情况,无需额外的条件判断。

相关问题