乘积小于 K 的子数组
2023-02-18 16:35:14 时间
乘积小于 K 的子数组
作者:Grey
原文地址:
题目链接
LeetCode 713. Subarray Product Less Than 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 * 10^4
1 <= nums[i] <= 1000
0 <= k <= 10^6
主要思路
由于题目要求中说明了,数组的元素都是正数。
说明区间累乘积和区间大小有单调性,
可以使用滑动窗口解法,如果L...R
区间内满足累乘积小于 k,那么必须以L
开头的满足乘积小于 k 的子数组有(R - L + 1)
个,
如下图:
假设L = 3,R = 7
,那么满足条件的子数组是:
[L...L]
,
[L...L+1]
,
[L...L+2]
,
[L...L+3]
,
[L...L+4]
,
正好R - L + 1 = 5
个。
接下来,继续求必须以L+1
开头的满足乘积小于 k 的子数组个数。
代码见:
class Solution {
public int numSubarrayProductLessThanK(int[] nums, int k) {
if (k <= 1) {
return 0;
}
int L = 0;
int R = 0;
int count = 0;
int base = 1;
while (R < nums.length) {
base *= nums[R];
while (base >= k) {
base /= nums[L++];
}
// L...R 满足条件
// R + 1 是第一个不满足的位置。
count += (R - L + 1);
R++;
}
return count;
}
}
时间复杂度O(N)
,空间复杂度O(1)
更多
相关文章
- 宝塔部分用户被挂马,官方建议暂时关闭面板
- 七天接手react项目 系列 —— 生命周期&受控和非受控组件&Dom 元素&Diffing 算法
- Redis的数据被删除,占用内存咋还那么大?
- Redis Cluster 原理说的头头是道,这些配置不懂就是纸上谈兵
- Redis进阶篇:发布订阅模式原理与运用
- Redis 内存优化神技,小内存保存大数据
- SpringBoot 集成缓存性能之王 Caffeine
- 掘地三尺搞定 Redis 与 MySQL 数据一致性问题
- Redis 的数据过期了就会马上删除么?
- Redis 为何使用近似 LRU 算法淘汰数据,而不是真实 LRU?
- Redis 内存满了怎么办?这样设置才正确!
- Redis HyperLogLog 是什么?这些场景使用它,让我枪出如龙,一笑破苍穹
- 硬核 | Redis 布隆(Bloom Filter)过滤器原理与实战
- Redis 缓存击穿(失效)、缓存穿透、缓存雪崩怎么解决?
- 别再用 Redis List 实现消息队列了,Stream 专为队列而生
- Redis 忽然变慢了如何排查并解决?
- 为什么你辛苦肝的博客没人看?搭框架、排版、画图技巧这些你真的懂么?
- Redis 竟然能用 List 实现消息队列
- Redis 事务支持 ACID 么?
- String 既然能做性能调优,我直呼内行