leetcode
leetcode 2901 ~ 2950
乘积小于 K 的子数组

乘积小于 K 的子数组

难度:

标签:

题目描述

English description is not available for the problem. Please switch to Chinese.

代码结果

运行时间: 81 ms, 内存: 18.1 MB

/*
 * 思路：
 * 使用Java Stream实现与普通Java代码类似的逻辑。
 * 由于Stream处理较为复杂的逻辑并不方便，我们还是采用滑动窗口算法。
 */
import java.util.stream.IntStream;
public class Solution {
    public int numSubarrayProductLessThanK(int[] nums, int k) {
        if (k <= 1) return 0;
        int[] count = {0};
        int[] product = {1};
        int[] start = {0};
        IntStream.range(0, nums.length).forEach(end -> {
            product[0] *= nums[end];
            while (product[0] >= k) {
                product[0] /= nums[start[0]++];
            }
            count[0] += end - start[0] + 1;
        });
        return count[0];
    }
}

解释

方法:

该题解采用了滑动窗口的方法来寻找所有乘积小于k的子数组。初始化两个指针left和right指向数组的起始位置，以及一个变量window_product来保存窗口内数字的乘积。向右移动right指针，扩大窗口，并更新window_product。如果window_product达到或超过了k，就逐渐移动left指针，缩小窗口，直到window_product小于k。每次当窗口的乘积有效（小于k）时，可以确定以right-1为结尾的子数组数量为right-left，因为每一个以right-1为结束点的子数组都有一个不同的起始点，这些起始点从left到right-1。因此，每次迭代中，都将这个长度加到结果answer中。

时间复杂度:

O(n)

空间复杂度:

O(1)

代码细节讲解

🦆
为什么在 k 小于等于 1 时直接返回 0 而不进一步处理数组中的元素？
▷
在 k 小于等于 1 的情况下，由于数组元素都是整数，最小的正整数是 1，乘积中包含任何正整数都会使得乘积不小于 1。因此，不存在任何非空子数组的乘积小于 1。直接返回 0 是因为根据题目的定义和数学逻辑，不可能有符合条件的子数组。
🦆
滑动窗口的方法如何确保没有遗漏任何一个乘积小于 k 的子数组？
▷
滑动窗口通过动态调整窗口的大小（通过移动左右指针），可以有效地探索所有可能的子数组。当增加窗口右边界（即向右扩展窗口）可能导致新的子数组产生时，每次窗口的乘积有效时（即小于 k），则可以确认以当前右边界-1（right-1）为结束点的所有子数组都符合条件。通过逐步移动左指针，直到窗口内的乘积小于 k，确保了每次都重新计算从新的左指针开始到右指针-1为止的所有子数组。这种方法确保了从每个可能的起始点到每个可能的终点的所有子数组都被考虑到，从而没有遗漏任何一个乘积小于 k 的子数组。
🦆
在窗口内乘积超过 k 时，为什么只是通过移动左指针来调整窗口大小，而不考虑其他方式如跳过某些元素？
▷
移动左指针来缩小窗口是一种有效的方式来降低窗口内的乘积，因为这种方法可以逐步减少乘积，直到窗口内的乘积再次小于 k。如果考虑跳过某些元素，可能会错过一些有效的子数组，因为即使当前元素使得乘积超标，该元素左侧或右侧可能存在许多符合条件的子数组。通过逐步移动左指针，我们可以确保考虑到从当前右指针开始的所有可能的子数组，而不会遗漏任何应该被计算的组合。

相关问题

使用最小花费爬楼梯打家劫舍