代码拉取完成,页面将自动刷新
同步操作将从 doocs/leetcode 强制同步,此操作会覆盖自 Fork 仓库以来所做的任何修改,且无法恢复!!!
确定后同步将在后台操作,完成时将刷新页面,请耐心等待。
给你一个整数数组 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]
为右端点的定界子数组的个数,然后将所有的个数相加即可。
具体实现逻辑如下:
[minK, maxK]
中的元素的下标 $k$,初始值为 $-1$。那么当前元素 nums[i]
的左端点一定大于 $k$。minK
的下标 $j_1$,最近一个值为 maxK
的下标 $j_2$,初始值均为 $-1$。那么当前元素 nums[i]
的左端点一定小于等于 $\min(j_1, j_2)$。时间复杂度 $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;
}
此处可能存在不合适展示的内容,页面不予展示。您可通过相关编辑功能自查并修改。
如您确认内容无涉及 不当用语 / 纯广告导流 / 暴力 / 低俗色情 / 侵权 / 盗版 / 虚假 / 无价值内容或违法国家有关法律法规的内容,可点击提交进行申诉,我们将尽快为您处理。