动态规划-子数组乘积小于k的总个数 Subarray Product Less Than K

2018-09-01 23:02:46

问题求解：

最开始的时候，一眼看过去就是一条 dp 嘛，保存每个数字结尾的长度和，最后求和就好，至于长度如何求，本题中需要用滑动窗口来维护。

很好的题目，将滑动窗口算法和动态规划巧妙的结合了起来。

    public int numSubarrayProductLessThanK(int[] nums, int k) {

        if (k <= 1) return 0;

        int res = 0;

        int begin = 0;

        int cur = 1;

        for (int end = 0; end < nums.length; end++) {

            cur *= nums[end];

            while (cur >= k) {

                cur /= nums[begin];

                begin++;

            }

            res += end - begin + 1;

        }

        return res;

    }

巴特西

动态规划-子数组乘积小于k的总个数 Subarray Product Less Than K

最新文章

热门文章