class Solution {
public:
long long countSubarrays(vector<int>& nums, int minK, int maxK) {
}
};
6207. 统计定界子数组的数目
给你一个整数数组 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原站题解
cpp 解法, 执行用时: 84 ms, 内存消耗: 68.8 MB, 提交时间: 2023-08-22 15:28:49
class Solution {
public:
long long countSubarrays(vector<int> &nums, int min_k, int max_k) {
long long ans = 0L;
int n = nums.size(), min_i = -1, max_i = -1, i0 = -1;
for (int i = 0; i < n; ++i) {
int x = nums[i];
if (x == min_k) min_i = i;
if (x == max_k) max_i = i;
if (x < min_k || x > max_k) i0 = i; // 子数组不能包含 nums[i0]
ans += max(min(min_i, max_i) - i0, 0);
}
return ans;
}
};
golang 解法, 执行用时: 80 ms, 内存消耗: 8.2 MB, 提交时间: 2023-08-22 15:28:31
func countSubarrays(nums []int, minK, maxK int) (ans int64) {
minI, maxI, i0 := -1, -1, -1
for i, x := range nums {
if x == minK {
minI = i
}
if x == maxK {
maxI = i
}
if x < minK || x > maxK {
i0 = i // 子数组不能包含 nums[i0]
}
ans += int64(max(min(minI, maxI)-i0, 0))
}
return
}
func min(a, b int) int { if b < a { return b }; return a }
func max(a, b int) int { if b > a { return b }; return a }
java 解法, 执行用时: 8 ms, 内存消耗: 55.3 MB, 提交时间: 2023-08-22 15:28:00
class Solution {
public long countSubarrays(int[] nums, int minK, int maxK) {
var ans = 0L;
int n = nums.length, minI = -1, maxI = -1, i0 = -1;
for (var i = 0; i < n; ++i) {
var x = nums[i];
if (x == minK) minI = i;
if (x == maxK) maxI = i;
if (x < minK || x > maxK) i0 = i; // 子数组不能包含 nums[i0]
ans += Math.max(Math.min(minI, maxI) - i0, 0);
}
return ans;
}
}
python3 解法, 执行用时: 236 ms, 内存消耗: 27.1 MB, 提交时间: 2023-08-22 15:27:40
class Solution:
def countSubarrays(self, nums: List[int], min_k: int, max_k: int) -> int:
ans = 0
min_i = max_i = i0 = -1
for i, x in enumerate(nums):
if x == min_k: min_i = i
if x == max_k: max_i = i
if not min_k <= x <= max_k: i0 = i # 子数组不能包含 nums[i0]
ans += max(min(min_i, max_i) - i0, 0)
# 注：上面这行代码，改为手动算 min max 会更快
# j = min_i if min_i < max_i else max_i
# if j > i0: ans += j - i0
return ans