共计 3687 个字符，预计需要花费 10 分钟才能阅读完成。
题目形容
这是 LeetCode 上的 795. 区间子数组个数 ，难度为 中等。
Tag :「模仿」、「枯燥栈」
给你一个整数数组 nums 和两个整数：left 及 right。
找出 nums 中间断、非空且其中最大元素在范畴 $[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 <= 10^5$
- $0 <= nums[i] <= 10^9$
- $0 <= left <= right <= 10^9$
枯燥栈
为了不便，咱们令 $[left, right]$ 为 $[a, b]$。
一个容易想到的思路是应用「枯燥栈」。
统计所有最大值范畴在 $[a, b]$ 之间的子数组个数，可等价为统计每一个范畴落在 $[a, b]$ 之间的 $nums[i]$ 作为最大值时子数组的个数。
由此能够进一步将问题转换为：求解每个 $nums[i]$ 作为子数组最大值时，最远的非法左右端点的地位。也就是求解每一个 $nums[i]$ 左右最近一个比其“大”的地位，这能够应用「枯燥栈」来进行求解。
对于枯燥栈不理解的同学，能够看前置 🧀 :【RMQ 专题】对于 RMQ 的若干解法
统计所有 $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)$
模仿
除了统计「每个 $nums[i]$ 作为子数组最大值时，所能奉献的子数组个数」以外，咱们还能够统计「每个 $nums[i]$ 作为子数组右端点时，所能奉献的子数组个数」。
具体的，咱们从前往后解决每个 $nums[i]$，并统计其作为子数组右端点时，所能奉献的子数组个数。同时应用变量 j 和 k 别离记录最近一次满足「$nums[i]$ 范畴落在 $[a, b]$ 之间」以及「$nums[i]$ 数值大于 $b$」的下标地位。
遍历过程中依据 $nums[i]$ 与规定范畴 $[a, b]$ 之间的关系进行分状况探讨：
- $nums[i]$ 大于 $b$，$nums[i]$ 作为右端点，必不可能奉献非法子数组。更新
k； - $nums[i]$ 小于 $a$，此时 $nums[i]$ 想作为右端点的话，子数组必须有其余满足「范畴落在 $[a, b]$ 之间」的其余数，而最近一个满足要求的地位为 $j$，若有 $j > k$，阐明范畴在 $(k, j]$ 均能作为子数组的左端点，累加计划数 $j – k$；若有 $j < k$，阐明咱们无奈找到任何一个左端点，使得造成的子数组满足要求（要么最值不在 $[a, b]$ 范畴内，要么有 $[a, b]$ 范畴内的数，但最大值又大于
b值）； - $nums[i]$ 落在范畴 $[a, b]$，此时 $nums[i]$ 想作为右端点的话，只须要找到右边第一个数值大于 $b$ 的数值即可（即变量
k），累加计划数 $i – 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(1)$
最初
这是咱们「刷穿 LeetCode」系列文章的第 No.795 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，局部是有锁题，咱们将先把所有不带锁的题目刷完。
在这个系列文章外面，除了解说解题思路以外，还会尽可能给出最为简洁的代码。如果波及通解还会相应的代码模板。
为了不便各位同学可能电脑上进行调试和提交代码，我建设了相干的仓库：https://github.com/SharingSou…。
在仓库地址里，你能够看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其余优选题解。
更多更全更热门的「口试 / 面试」相干材料可拜访排版精美的 合集新基地 🎉🎉
本文由 mdnice 多平台公布