LeetCode 713. 乘积小于 K 的子数组
题目描述
题意分析
统计乘积严格小于
k的连续非空子数组数量。每个数组元素都是至少为1的正整数，因此加入新因子不会让乘积减小，移除左侧因子也不会让乘积增大，可以利用滑动窗口。题目要求统计所有满足条件的区间，而不是只找最长或最短的一段。固定右端点后，若已经找到最靠左的合法起点，那么从它到右端点之间的所有起点，都能各形成一个合法子数组。
解法：正数乘积滑动窗口
核心思路
[!blue]
用
left、right表示窗口，用product保存其中所有元素的乘积。乘法的初始值为1。每次右端加入一个数后，如果product >= k，就不断除去当前左端因子并右移left，直到严格小于k。左边界不需要回退。之前被移除的更早起点，当时已使乘积至少为
k；继续往右加入大于等于一的因子后，只会维持或增大这个乘积，不可能重新合法。因此收缩完成时，left就是以当前右端点结尾的最早合法起点。窗口合法后，它的任意非空后缀也合法，因为继续删除若干左侧因子不会使乘积增大。合法起点恰好是
left到right，一共有right - left + 1个，将这部分一次性加入答案即可。每个子数组只在自己的右端点被处理时计数，不会重复。当
k <= 1，任何非空正整数子数组的乘积都至少为一，直接返回零。这样后续保证k > 1，即使某个单独元素太大，窗口也能一直缩到空，此时乘积恢复为1，循环停止，长度贡献自然为零。因子等于一时，除掉它不会让乘积下降，但左指针仍在前进，所以必须持续使用循环，而不能只删除一次。左右指针都只向右移动，每个元素最多加入和移出一次。
解题步骤
- 若
k <= 1，直接返回0。- 初始化
left = 0、product = 1、答案为0。- 每次移动右端点，先将新值乘入
product。- 只要乘积大于等于
k，先除掉nums[left]，再推进左边界。- 将恢复合法后的
right - left + 1加入答案，遍历结束返回总数。
代码实现
class Solution {
// 当窗口乘积大于等于 k 时，持续移动左指针并除掉左端元素，直到窗口重新满足条件。
public int numSubarrayProductLessThanK(int[] nums, int k) {
// 非空正整数乘积至少一，此时没有合法子数组
if (k <= 1) {
return 0;
}
int left = 0;
long product = 1;
int res = 0;
for (int right = 0; right < nums.length; right++) {
product *= nums[right];
while (product >= k) {
// 先移除旧左端因子，再推进左边界
product /= nums[left];
left++;
}
// 合法窗口内每个起点都产生一个以当前右端结尾的子数组
res += right - left + 1;
}
return res;
}
}
func numSubarrayProductLessThanK(nums []int, k int) int {
// 当窗口乘积大于等于 k 时，持续移动左指针并除掉左端元素，直到窗口重新满足条件。
// 非空正整数乘积至少一，此时没有合法子数组
if k <= 1 {
return 0
}
left := 0
product := 1
res := 0
for right, val := range nums {
product *= val
for product >= k {
// 先移除旧左端因子，再推进左边界
product /= nums[left]
left++
}
// 合法窗口内每个起点都产生一个以当前右端结尾的子数组
res += right - left + 1
}
return res
}
复杂度分析
- 时间复杂度：$O(n)$，两端各自最多向前移动 n 次。
- 空间复杂度：$O(1)$，只维护窗口与计数。
关键点总结
[!green]
- 移除一不一定让乘积下降，但左指针仍前进，最终能收缩为空。
- 空窗口乘积为一，当前贡献自然为零。
易错点总结
[!yellow]
- 严格小于误写为允许相等，会多计边界乘积。
- 只收缩一次，可能留下仍不合法的窗口。
- 先移动左下标再除，会除掉错误的因子。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 209. 长度最小的子数组 | 中等 | 同样利用正数建立窗口单调性，原题求最短长度，本题通过合法后缀长度累计数量。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！