LeetCode Subarray Product Less Than K 题解 双指针+单调性

题意

给定一个正整数数组和K，数有多少个连续子数组满足：
数组中所有的元素的积小于K.

思路

依旧是双指针的思路
我们首先固定右指针r.
现在子数组的最右边的元素是nums[r].
我们让这个子数组尽可能的长，尽可能的往左边拓展，假设最左边的元素的前一个元素是l.
即子数组(l,r].
显然对于以nums[r]结尾的满足题意的数组个数为 $r-l$r−l
对于
(l1​,r1​],(l2​,r2​](r1​<r2​)
由于数组元素都是正数，易证
$l_1\&lt;l_2$l1​<l2​
举个例子(其实证明也是这个反正的思路)：
加入(2,5]和(1,6]同时存在。

1. (2,5] 第5个数结尾，左边最多到第2个。 ①
2. (1,6] 第6个数结尾，左边最多到第1个。
   那么换句话第一个数到第五个数的乘积肯定不超过k，那和①这一行的(2,5]矛盾了。
   因此l关于r是非严格单调递增（换句话说不下降）的。
   明白了这一点就可以具体的设计了。

由r快速转移到r+1的状态

假设对于r我们已经求得了(l,r]。
那么对于r+1的问题，我们如何快速转移求解呢？

1. 更新product，乘以新增的nums[r]
2. 基于单调性，我们只需从上一步r的l开始验证，如果不符合则l后移

复杂度

$T\left(N\right)=O\left(N\right),M\left(N\right)=O\left(1\right)$T(N)=O(N),M(N)=O(1)

结果

(14ms, 80.5%, 52.7MB, 100.00%)

Source Code

class Solution {
    public int numSubarrayProductLessThanK(int[] nums, int k) {
        int len = nums.length;
        int product = 1;
        int count = 0;
        // (l,r]
        int l = -1, r = 0;
        while (r < len) {
            product *= nums[r];
            while (l < r && product >= k)
                product /= nums[++l];
            count += r - l;
            ++r;
        }
        return count;
    }
}

参考链接

有了思路之后，还参考了GrandYang的博客