线性动态规划：乘积小于K的子数组个数

题目描述
给定一个正整数数组 nums 和一个整数 k，要求统计并返回该数组中乘积小于 k 的连续子数组的个数。

示例 1
输入：nums = [10, 5, 2, 6]，k = 100
输出：8
解释：乘积小于 100 的连续子数组包括：
[10]、[5]、[2]、[6]、[10,5]、[5,2]、[2,6]、[5,2,6]
注意 [10,5,2] 的乘积是 100，不小于 100，因此不计数。

示例 2
输入：nums = [1, 2, 3]，k = 0
输出：0
解释：因为 k=0，任何正整数的乘积都不小于 0，所以结果为 0。

注意

1. 数组元素均为正整数。
2. 子数组必须是连续的。
3. 如果 k ≤ 1，则结果一定为 0（因为正整数的最小乘积是 1）。

解题过程

步骤1：问题理解与暴力法思路
最直接的思路是枚举所有连续子数组，计算每个子数组的乘积，若乘积小于 k 则计数。
设数组长度为 n，子数组个数为 O(n²)，每个子数组计算乘积需 O(长度)，总时间复杂度为 O(n³)，显然不可行。
优化：在枚举时可以边扩展边计算乘积，但仍然是 O(n²) 时间复杂度，当 n 较大时（如 10⁵）依然会超时。

步骤2：滑动窗口 + 双指针的思想
由于数组元素均为正整数，乘积具有单调性：

• 对于固定的左指针 left，右指针 right 向右移动时，子数组乘积单调递增。
• 一旦乘积 ≥ k，再向右扩展只会让乘积更大，因此可以停止扩展右指针，并移动左指针缩小窗口。

这提示我们可以用滑动窗口维护一个乘积 < k 的连续子数组，并计算以右指针结尾的满足条件的子数组个数。

步骤3：推导计数方法
假设当前窗口为 [left, right]，其乘积 < k。
对于这个窗口，以 right 结尾且乘积 < k 的子数组有多少个？
这些子数组必须从 left 到 right 之间的某个位置开始，到 right 结束。
具体来说，从 left, left+1, ..., right 开始，到 right 结束的子数组都满足乘积 < k（因为乘积单调递增，起点越靠右乘积越小，所以都小于 k）。
这样的子数组个数 = right - left + 1。
因此，每次右指针右移一位，只要当前窗口乘积 < k，就累加 right - left + 1 到答案中。

步骤4：算法步骤

1. 初始化 left = 0，当前乘积 product = 1，答案 count = 0。
2. 用右指针 right 从 0 到 n-1 遍历数组：
   a. 将 nums[right] 乘到 product 上。
   b. 若 product >= k，则移动左指针 left 直到 product < k（每次移动时，将 nums[left] 从 product 中除掉，然后 left++）。
   c. 此时窗口 [left, right] 的乘积 < k，累加 right - left + 1 到 count。
3. 返回 count。

步骤5：示例推演
以 nums = [10, 5, 2, 6]，k = 100 为例：

• right=0：product=10，left=0，窗口 [0,0]，累加 1。
• right=1：product=50，left=0，窗口 [0,1]，累加 2（子数组 [5]、[10,5]）。
• right=2：product=100，乘积 ≥ k，移动左指针：
  • 除以 nums[0]=10，product=10，left=1，乘积 10<100，停止移动。
  • 窗口 [1,2]，累加 2（子数组 [2]、[5,2]）。
• right=3：product=60，left=1，窗口 [1,3]，累加 3（子数组 [6]、[2,6]、[5,2,6]）。
  累计：1+2+2+3 = 8。

步骤6：边界条件与细节

• 如果 k ≤ 1，因为正整数乘积至少为 1，所以没有乘积 < k 的子数组，直接返回 0。
• 在移动左指针时，要确保 left ≤ right，如果 left > right，说明单个元素就 ≥ k，此时乘积应重置为 1，窗口为空，下一次循环会重新从 right+1 开始。
• 时间复杂度 O(n)：每个元素最多被左指针和右指针各访问一次。
• 空间复杂度 O(1)。

步骤7：代码框架（Python风格）

def numSubarrayProductLessThanK(nums, k):
    if k <= 1:
        return 0
    left = 0
    product = 1
    count = 0
    for right, num in enumerate(nums):
        product *= num
        while product >= k:
            product //= nums[left]
            left += 1
        count += (right - left + 1)
    return count

步骤8：思考扩展

• 如果数组包含零或负数，滑动窗口的单调性不再成立，问题会更复杂，需结合前缀积和二分搜索，时间复杂度 O(n log n)。
• 类似问题：求和小于 k 的子数组个数，同样可用滑动窗口，因为正数求和也是单调的。