题目描述
这是 LeetCode 上的 795. 区间子数组个数 ,难度为 中等 。
Tag : 「模拟」、「 单调栈 」
给你一个整数数组 nums 和两个整数:left 及 right 。
找出 nums 中连续、非空且其中最大元素在范围 [left,right][left, right][left,right] 内的子数组,并返回满足条件的子数组的个数。
生成的 测试用例 保证结果符合 32-bit 整数范围。
示例 1:
输入:nums = [2,1,4,3], left = 2, right = 3
输出:3
解释:满足条件的三个子数组:[2], [2, 1], [3]
复制代码
示例 2:
输入:nums = [2,9,2,5,6], left = 2, right = 8
输出:7
复制代码
提示:
- 1<=nums.length<=1051 <= nums.length <= 10^51<=nums.length<=105
- 0<=nums[i]<=1090 <= nums[i] <= 10^90<=nums[i]<=109
- 0<=left<=right<=1090 <= left <= right <= 10^90<=left<=right<=109
单调栈
为了方便,我们令 [left,right][left, right][left,right] 为 [a,b][a, b][a,b]。
一个容易想到的思路是使用「单调栈」。
统计所有最大值范围在 [a,b][a, b][a,b] 之间的子数组个数,可等价为统计每一个范围落在 [a,b][a, b][a,b] 之间的 nums[i]nums[i]nums[i] 作为最大值时子数组的个数。
由此可以进一步将问题转换为:求解每个 nums[i]nums[i]nums[i] 作为子数组最大值时,最远的合法左右端点的位置。也就是求解每一个 nums[i]nums[i]nums[i] 左右最近一个比其“大”的位置,这可以使用「单调栈」来进行求解。
统计所有 nums[i]nums[i]nums[i] 对答案的贡献即是最终答案,但我们忽略了「当 nums 存在重复元素,且该元素作为子数组最大值时,最远左右端点的边界越过重复元素时,导致重复统计子数组」的问题。
我们不失一般性的举个 来理解(下图):
为了消除这种重复统计,我们可以将「最远左右边界」的一端,从「严格小于」调整为「小于等于」,从而实现半开半闭的效果。
Java 代码:
class Solution {
public int numSubarrayBoundedMax(int[] nums, int a, int b) {
int n = nums.length, ans = 0;
int[] l = new int[n + 10], r = new int[n + 10];
Arrays.fill(l, -1); Arrays.fill(r, n);
Deque<Integer> d = new ArrayDeque<>();
for (int i = 0; i < n; i++) {
while (!d.isEmpty() && nums[d.peekLast()] < nums[i]) r[d.pollLast()] = i;
d.addLast(i);
}
d.clear();
for (int i = n - 1; i >= 0; i--) {
while (!d.isEmpty() && nums[d.peekLast()] <= nums[i]) l[d.pollLast()] = i;
d.addLast(i);
}
for (int i = 0; i < n; i++) {
if (nums[i] < a || nums[i] > b) continue;
ans += (i - l[i]) * (r[i] - i);
}
return ans;
}
}
复制代码
TypeScript 代码:
function numSubarrayBoundedMax(nums: number [], a: number, b: number): number {
let n = nums.length, ans = 0
const l = new Array<number>(n).fill(-1), r = new Array<number>(n).fill(n)
let stk = new Array<number>()
for (let i = 0; i < n; i++) {
while (stk.length > 0 && nums[stk[stk.length - 1]] < nums[i]) r[stk.pop()] = i
stk.push(i)
}
stk = new Array<number>()
for (let i = n - 1; i >= 0; i--) {
while (stk.length > 0 && nums[stk[stk.length - 1]] <= nums[i]) l[stk.pop()] = i
stk.push(i)
}
for (let i = 0; i < n; i++) {
if (nums[i] < a || nums[i] > b) continue
ans += (i - l[i]) * (r[i] - i)
}
return ans
}
复制代码
Python3 代码:
class Solution:
def numSubarrayBoundedMax(self, nums: List[int], a: int, b: int) -> int:
n, ans = len(nums), 0
l, r = [-1] * n, [n] * n
stk = []
for i in range(n):
while stk and nums[stk[-1]] < nums[i]:
r[stk.pop()] = i
stk.append(i)
stk = []
for i in range(n - 1, -1, -1):
while stk and nums[stk[-1]] <= nums[i]:
l[stk.pop()] = i
stk.append(i)
for i in range(n):
if a <= nums[i] <= b:
ans += (i - l[i]) * (r[i] - i)
return ans
复制代码
- 时间复杂度:O(n)O(n)O(n)
- 空间复杂度:O(n)O(n)O(n)
模拟
除了统计「每个 nums[i]nums[i]nums[i] 作为子数组最大值时,所能贡献的子数组个数」以外,我们还可以统计「每个 nums[i]nums[i]nums[i] 作为子数组右端点时,所能贡献的子数组个数」。
具体的,我们从前往后处理每个 nums[i]nums[i]nums[i],并统计其作为子数组右端点时,所能贡献的子数组个数。同时使用变量 j 和 k 分别记录最近一次满足「nums[i]nums[i]nums[i] 范围落在 [a,b][a, b][a,b] 之间」以及「nums[i]nums[i]nums[i] 数值大于 bbb」的下标位置。
遍历过程中根据 nums[i]nums[i]nums[i] 与规定范围 [a,b][a, b][a,b] 之间的关系进行分情况讨论:
- nums[i]nums[i]nums[i] 大于 bbb,nums[i]nums[i]nums[i] 作为右端点,必不可能贡献合法子数组。更新 k;
- nums[i]nums[i]nums[i] 小于 aaa,此时 nums[i]nums[i]nums[i] 想作为右端点的话,子数组必须有其他满足「范围落在 [a,b][a, b][a,b] 之间」的其他数,而最近一个满足要求的位置为 jjj,若有 j>kj > kj>k,说明范围在 (k,j](k, j](k,j] 均能作为子数组的左端点,累加方案数 j−kj – kj−k;若有 j<kj < kj<k,说明我们无法找到任何一个左端点,使得形成的子数组满足要求(要么最值不在 [a,b][a, b][a,b] 范围内,要么有 [a,b][a, b][a,b] 范围内的数,但最大值又大于 b 值);
- nums[i]nums[i]nums[i] 落在范围 [a,b][a, b][a,b],此时 nums[i]nums[i]nums[i] 想作为右端点的话,只需要找到左边第一个数值大于 bbb 的数值即可(即变量 k),累加方案数 i−ki – ki−k。更新 j。
Java 代码:
class Solution {
public int numSubarrayBoundedMax(int[] nums, int a, int b) {
int n = nums.length, ans = 0;
for (int i = 0, j = -1, k = -1; i < n; i++) {
if (nums[i] > b) {
k = i;
} else {
if (nums[i] < a) {
if (j > k) ans += j - k;
} else {
ans += i - k;
j = i;
}
}
}
return ans;
}
}
复制代码
TypeScript 代码:
function numSubarrayBoundedMax(nums: number[], a: number, b: number): number {
let n = nums.length, ans = 0
for (let i = 0, j = -1, k = -1; i < n; i++) {
if (nums[i] > b) {
k = i
} else {
if (nums[i] < a) {
if (j > k) ans += j - k
} else {
ans += i - k
j = i
}
}
}
return ans
}
复制代码
Python3 代码:
class Solution:
def numSubarrayBoundedMax(self, nums: List[int], a: int, b: int) -> int:
n, ans = len(nums), 0
j, k = -1, -1
for i in range(n):
if nums[i] > b:
k = i
else:
if nums[i] < a:
ans += j - k if j > k else 0
else:
ans += i - k
j = i
return ans
复制代码
- 时间复杂度:O(n)O(n)O(n)
- 空间复杂度:O(1)O(1)O(1)
最后
这是我们「刷穿 LeetCode」系列文章的第 No.795 篇,系列开始于 2021/01/01,截止于起始日 LeetCode 上共有 1916 道题目,部分是有锁题,我们将先把所有不带锁的题目刷完。
在这个系列文章里面,除了讲解解题思路以外,还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。