难度: Medium
Submission
运行时间: 51 ms
内存: 30.5 MB
class Solution:
def countSubarrays(self, nums: List[int]) -> int:
last = inf
res = l = 0
for i, n in enumerate(chain(nums, [-inf])):
if n <= last:
res += (i-l)*(i-l+1)//2
l = i
last = n
return res
Explain
该题解采用了一种单遍扫描的方法来解决问题。首先，初始化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)
class Solution:
def countSubarrays(self, nums: List[int]) -> int:
last = inf # 上一个元素的值，初始为无穷大
res = l = 0 # res是最终结果，l是当前递增子数组的起始位置
for i, n in enumerate(chain(nums, [-inf])): # 在数组末尾加一个-∞来处理边界
if n <= last: # 如果当前元素不大于上一个元素
res += (i-l)*(i-l+1)//2 # 计算从l到i-1的递增子数组的数量，并累加到结果中
l = i # 更新当前递增子数组的起始位置为i
last = n # 更新last为当前元素
return res # 返回计算的结果
Explore
在数组末尾添加一个无穷小(-inf)元素主要是为了处理数组结束时的边界情况。在算法中，我们需要在发现当前元素不大于前一个元素时计算递增子数组的数量。如果不添加这个-∞元素，那么在数组正常结束后，我们需要额外的逻辑来处理最后一个递增子数组的计算，因为最后一段递增子数组不会因为一个较小的元素而被终止。通过添加-∞，可以保证这个逻辑也适用于数组的最后一个元素，使得代码更加简洁和统一。
这个公式是基于组合数学中的计数原理得到的。考虑从位置`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`。
这种逻辑可以有效处理数组的开始和结束的边界情况。对于数组的开始，由于`last`初值设为无穷大，任何数组中的第一个元素都不会大于`last`，因此算法可以从第一个正常的递增子数组开始计算。对于数组的结束，通过在数组末尾添加一个无穷小(-inf)元素，可以确保最后一个递增子数组被正确计算。这是因为这个-∞元素肯定不大于前一个元素，从而触发计算最后一段递增子数组的逻辑。因此，这个检查机制可以在遍历中自然地处理所有边界情况，无需额外的条件判断。