脚本宝典收集整理的这篇文章主要介绍了LeetCode每日一题——713. 乘积小于 K 的子数组（滑动窗口），脚本宝典觉得挺不错的，现在分享给大家，也给大家做个参考。
给你一个整数数组 nums 和一个整数 k ，请你返回子数组内所有元素的乘积严格小于 k 的连续子数组的数目。
示例 1：
输入：nums = [10,5,2,6], k = 100输出：8解释：8 个乘积小于 100 的子数组分别为：[10]、[5]、[2],、[6]、[10,5]、[5,2]、[2,6]、[5,2,6]。需要注意的是 [10,5,2] 并不是乘积小于 100 的子数组。示例 2：
输入：nums = [1,2,3], k = 0输出：0
提示:
1 <= nums.length <= 3 * 1041 <= nums[i] <= 10000 <= k <= 106
1 import java.util.*; 2 import java.math.*; 3 4 class Solution { 5 6 int N = 30000 + 10; 7 8 PRivate BigDecimal[] pre = new BigDecimal[N]; 9 10 public int numSubarrayProductLessThanK(int[] nums, int k) { 11 // @R_245_1304@: O(nLOGn) 12 // 性质：前缀乘积递增，可以用二分 13 // 暴力+前缀和 14 if (k == 0) { 15 return 0; 16 } 17 int n = nums.length; 18 pre[0] = BigDecimal.ONE; 19 for (int i = 1; i <= n; i++) { 20 pre[i] = pre[i - 1].multiply(new BigDecimal(String.valueOf(nums[i - 1]))); 21 } 22 23 int cnt = 0; 24 // 枚举每一个左边界 25 for (int i = 1; i <= n; i++) { 26 // 二分 27 int left = i; 28 int right = n; 29 while (left <= right) { 30 int mid = (left + right) >> 1; 31 if (check(i, mid, k)) { 32 left = mid + 1; 33 } else { 34 right = mid - 1; 35 } 36 } 37 // 有可能一个都不满足的情况 38 if (right >= i) { 39 cnt += (right - i + 1); 40 } 41 } 42 return cnt; 43 } 44 45 public boolean check(int left, int right, int k) { 46 int result = pre[right].divide(pre[left - 1]).COMpareTo(new BigDecimal(String.valueOf(k))); 47 return result < 0 ? true : false; 48 } 49 }
1 class Solution { 2 public int numSubarrayProductLessThanK(int[] nums, int k) { 3 if (k == 0 || k == 1) { 4 return 0; 5 } 6 int n = nums.length; 7 // 滑动窗口 8 int curMutil = 1; 9 int cnt = 0; 10 Deque<Integer> deque = new LinkedList<>(); 11 for (int i = 1; i <= n; i++) { 12 while (deque.size() > 0 && curMutil * nums[i - 1] >= k) { 13 curMutil /= nums[deque.getFirst() - 1]; 14 deque.pollFirst(); 15 } 16 if (curMutil * nums[i - 1] < k) { 17 curMutil *= nums[i - 1]; 18 deque.offerLast(i); 19 // 每次多一个区间的长度个数 20 cnt += (deque.getLast() - deque.getFirst() + 1); 21 } 22 } 23 24 return cnt; 25 } 26 }
力扣链接：https://leetcode.cn/problems/subarray-product-less-than-k/
以上是脚本宝典为你收集整理的LeetCode每日一题——713. 乘积小于 K 的子数组（滑动窗口）全部内容，希望文章能够帮你解决LeetCode每日一题——713. 乘积小于 K 的子数组（滑动窗口）所遇到的问题。
本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ：384754419，请注明来意。