Question

2444. 统计定界子数组的数目

English Version

题目描述

给你一个整数数组 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 <= 105
• 1 <= nums[i], minK, maxK <= 106

解法

方法一：枚举右端点

由题意，我们可以知道，定界子数组的所有元素都在区间 [minK, maxK] 中，且最小值一定为 minK，最大值一定为 maxK。

我们遍历数组 $nums$，统计以 nums[i] 为右端点的定界子数组的个数，然后将所有的个数相加即可。

具体实现逻辑如下：

1. 维护最近一个不在区间 [minK, maxK] 中的元素的下标 $k$，初始值为 $-1$。那么当前元素 nums[i] 的左端点一定大于 $k$。
2. 维护最近一个值为 minK 的下标 $j_1$，最近一个值为 maxK 的下标 $j_2$，初始值均为 $-1$。那么当前元素 nums[i] 的左端点一定小于等于 $\min(j_1, j_2)$。
3. 综上可知，以当前元素为右端点的定界子数组的个数为 $\max(0, \min(j_1, j_2) - k)$。累加所有的个数即可。

时间复杂度 $O(n)$，空间复杂度 $O(1)$。其中 $n$ 为数组 $nums$ 的长度。

class Solution:
  def countSubarrays(self, nums: List[int], minK: int, maxK: int) -> int:
    j1 = j2 = k = -1
    ans = 0
    for i, v in enumerate(nums):
      if v < minK or v > maxK:
        k = i
      if v == minK:
        j1 = i
      if v == maxK:
        j2 = i
      ans += max(0, min(j1, j2) - k)
    return ans

class Solution {
  public long countSubarrays(int[] nums, int minK, int maxK) {
    long ans = 0;
    int j1 = -1, j2 = -1, k = -1;
    for (int i = 0; i < nums.length; ++i) {
      if (nums[i] < minK || nums[i] > maxK) {
        k = i;
      }
      if (nums[i] == minK) {
        j1 = i;
      }
      if (nums[i] == maxK) {
        j2 = i;
      }
      ans += Math.max(0, Math.min(j1, j2) - k);
    }
    return ans;
  }
}

class Solution {
public:
  long long countSubarrays(vector<int>& nums, int minK, int maxK) {
    long long ans = 0;
    int j1 = -1, j2 = -1, k = -1;
    for (int i = 0; i < nums.size(); ++i) {
      if (nums[i] < minK || nums[i] > maxK) k = i;
      if (nums[i] == minK) j1 = i;
      if (nums[i] == maxK) j2 = i;
      ans += max(0, min(j1, j2) - k);
    }
    return ans;
  }
};

func countSubarrays(nums []int, minK int, maxK int) int64 {
  ans := 0
  j1, j2, k := -1, -1, -1
  for i, v := range nums {
    if v < minK || v > maxK {
      k = i
    }
    if v == minK {
      j1 = i
    }
    if v == maxK {
      j2 = i
    }
    ans += max(0, min(j1, j2)-k)
  }
  return int64(ans)
}

function countSubarrays(nums: number[], minK: number, maxK: number): number {
  let res = 0;
  let minIndex = -1;
  let maxIndex = -1;
  let k = -1;
  nums.forEach((num, i) => {
    if (num === minK) {
      minIndex = i;
    }
    if (num === maxK) {
      maxIndex = i;
    }
    if (num < minK || num > maxK) {
      k = i;
    }
    res += Math.max(Math.min(minIndex, maxIndex) - k, 0);
  });
  return res;
}

impl Solution {
  pub fn count_subarrays(nums: Vec<i32>, min_k: i32, max_k: i32) -> i64 {
    let mut res = 0;
    let mut min_index = -1;
    let mut max_index = -1;
    let mut k = -1;
    for i in 0..nums.len() {
      let num = nums[i];
      let i = i as i64;
      if num == min_k {
        min_index = i;
      }
      if num == max_k {
        max_index = i;
      }
      if num < min_k || num > max_k {
        k = i;
      }
      res += (0).max(min_index.min(max_index) - k);
    }
    res
  }
}

#define max(a, b) (((a) > (b)) ? (a) : (b))
#define min(a, b) (((a) < (b)) ? (a) : (b))

long long countSubarrays(int* nums, int numsSize, int minK, int maxK) {
  long long res = 0;
  int minIndex = -1;
  int maxIndex = -1;
  int k = -1;
  for (int i = 0; i < numsSize; i++) {
    int num = nums[i];
    if (num == minK) {
      minIndex = i;
    }
    if (num == maxK) {
      maxIndex = i;
    }
    if (num < minK || num > maxK) {
      k = i;
    }
    res += max(min(minIndex, maxIndex) - k, 0);
  }
  return res;
}