难度: Hard
给你一个整数数组 nums 和两个整数 minK 以及 maxK 。
nums 的定界子数组是满足下述条件的一个子数组：
minK 。maxK 。返回定界子数组的数目。
子数组是数组中的一个连续部分。
示例 1：
输入：nums = [1,3,5,2,7,5], minK = 1, maxK = 5 输出：2 解释：定界子数组是 [1,3,5] 和 [1,3,5,2] 。
示例 2：
输入：nums = [1,1,1,1], minK = 1, maxK = 1 输出：10 解释：nums 的每个子数组都是一个定界子数组。共有 10 个子数组。
提示：
2 <= nums.length <= 1051 <= nums[i], minK, maxK <= 106运行时间: 108 ms
内存: 26.7 MB
class Solution:
def countSubarrays(self, nums: List[int], minK: int, maxK: int) -> int:
premin, premax = -1, -1
l = 0
ans = 0
for r, x in enumerate(nums):
if x < minK or x > maxK:
premin, premax = -1, -1
l = r + 1
continue
if x == minK:
premin = r
if x == maxK:
premax = r
if premin != -1 and premax != -1:
ans += (premin if premin < premax else premax) - l + 1
return ans
此题解采用滑动窗口的策略，通过一次遍历来统计符合条件的子数组。对于数组中的每一个元素，我们维护两个变量 premin 和 premax 来记录满足条件 minK 和 maxK 的最近的索引位置。当遍历到的元素值小于 minK 或大于 maxK 时，说明当前元素不能被包含在任何有效的子数组中，此时需要重置 premin、premax，并将左指针 l 移动到当前右指针的下一个位置。如果当前元素等于 minK 或 maxK，则更新 premin 或 premax 的值。只有当 premin 和 premax 都被有效更新后，才计算当前的右指针 r 到左指针 l 之间的符合条件的子数组数量，增加的数量为 min(premin, premax) - l + 1。
时间复杂度: O(n)
空间复杂度: O(1)
class Solution:
def countSubarrays(self, nums: List[int], minK: int, maxK: int) -> int:
premin, premax = -1, -1 # 初始化 premin 和 premax
l = 0 # 初始化左指针
ans = 0 # 存储定界子数组的数量
for r, x in enumerate(nums): # 遍历数组元素及其索引
if x < minK or x > maxK: # 元素不在[minK, maxK]范围内
premin, premax = -1, -1 # 重置 premin 和 premax
l = r + 1 # 移动左指针
continue
if x == minK: # 更新 minK 的最新位置
premin = r
if x == maxK: # 更新 maxK 的最新位置
premax = r
if premin != -1 and premax != -1: # premin 和 premax 都有效时
ans += (premin if premin < premax else premax) - l + 1 # 计算定界子数组的数量
return ans # 返回结果
滑动窗口方法适用于这个问题因为它能有效地在单次遍历中处理和更新子数组的边界条件。这个问题要求找到所有包含特定最小值和最大值的子数组，而滑动窗口可以灵活地调整窗口的大小来直接应对数组中值的变化，尤其是当数组元素不符合[minK, maxK]范围时快速调整。动态规划通常适用于求解最优子结构问题，而这里需要连续跟踪最小和最大索引的更新，分治算法则适用于可以被分解为独立子问题的情况，但本题中子数组的界定高度依赖于全局的元素分布，因此滑动窗口在此更为高效且直接。
不会导致子数组被遗漏。当元素值不在[minK, maxK]范围内时，任何包含该元素的子数组都不能满足题目要求。因此，重置premin和premax是必要的，因为它们记录的是有效子数组的潜在起点。重置操作后，左指针l移至当前元素的下一个位置，这意味着所有之前可能的、但现在已无效的子数组界定被清除，新的搜索从一个清洁的状态开始，确保所有有效的子数组都能被正确统计，而无效的不会被错误地包含。
是的，该方法可以在所有情况下正确计算定界子数组的数量。这是因为只有当premin和premax都有效时（即都已经遇到了至少一次minK和maxK），才开始计算子数组的数量。这种计算方式确保只有包含了至少一个minK和一个maxK的子数组才被计算。此外，通过计算min(premin, premax) - l + 1，确保了即使在元素重复或极端分布的情况下，所有可能的子数组都能被考虑。这种方法准确地反映了从当前左指针到有效的最小/最大值索引之间的所有子数组，无论数组元素如何分布。