JZX轻语：简
LeetCode 713 - 乘积小于K的子数组
发表于2024年04月18日
使用一个滑动窗口维护当前乘积小于k的最长连续子数组。每当窗口右侧向右扩展一个元素时，结果(有效子数组数量)加上新窗口的长度(即，新增了以窗口当前右侧元素结尾的长度为1,2,…,滑动窗口大小的数组)。当窗口无法向右扩展时，则左侧边界向右移动以减少乘积，直到下一次尝试向右扩展成功。
class Solution:
def numSubarrayProductLessThanK(self, nums: List[int], k: int) -> int:
if k == 0:
return 0
result = 0
# 窗口的边界
left = 0 # 左侧包含
right = 0 # 右侧不包含
window_product = 1 # 空窗口的乘积设为1, 以方便乘
while right < len(nums):
if window_product * nums[right] < k: # 尝试扩展右边界
result += right - left + 1
window_product *= nums[right]
right += 1
else: # 否则, 收缩左边界
window_product //= nums[left]
left += 1
if right < left: # 如果窗口已经为空, 需要同步移动右边界, 并将窗口乘积重置为1
right = left
window_product = 1
return result