Rust）

作者 endlesscheng

2023年12月10日 12:08

⚠注意：题目说的最大元素指整个 $\textit{nums}$ 数组的最大值，不是子数组的最大值。

由于子数组越长，包含的元素越多，越能满足题目要求；反之，子数组越短，包含的元素越少，越不能满足题目要求。有这种性质的题目，可以用滑动窗口解决。

设 $\textit{mx} = \max(\textit{nums})$。
元素 $x=\textit{nums}[\textit{right}]$ 进入窗口时，如果 $x=\textit{mx}$，把计数器 $\textit{cntMx}$ 加一。
如果 $\textit{cntMx}=k$，则不断右移左指针 $\textit{left}$，直到窗口中的 $\textit{mx}$ 的出现次数小于 $k$ 为止。
内层循环结束后，$[\textit{left},\textit{right}]$ 这个子数组是不满足题目要求的，但在退出循环之前的最后一轮循环，$[\textit{left}-1,\textit{right}]$ 是满足题目要求的。由于子数组越长，越能满足题目要求，所以除了 $[\textit{left}-1,\textit{right}]$，还有 $[\textit{left}-2,\textit{right}],[\textit{left}-3,\textit{right}],\ldots,[0,\textit{right}]$ 都是满足要求的。也就是说，当右端点固定在 $\textit{right}$ 时，左端点在 $0,1,2,\ldots,\textit{left}-1$ 的所有子数组都是满足要求的，这一共有 $\textit{left}$ 个，加到答案中。

例如示例 1，当右端点移到第二个 $3$ 时，左端点移到 $2$，此时 $[1,3,2,3]$ 和 $[3,2,3]$ 是满足要求的。当右端点移到第三个 $3$ 时，左端点也移到第三个 $3$，此时 $[1,3,2,3,3], [3,2,3,3], [2,3,3], [3,3]$ 都是满足要求的。所以答案为 $2+4=6$。

###py

class Solution:
    def countSubarrays(self, nums: List[int], k: int) -> int:
        mx = max(nums)
        ans = cnt_mx = left = 0
        for x in nums:
            if x == mx:
                cnt_mx += 1
            while cnt_mx == k:
                if nums[left] == mx:
                    cnt_mx -= 1
                left += 1
            ans += left
        return ans

###java

class Solution {
    public long countSubarrays(int[] nums, int k) {
        int mx = 0;
        for (int x : nums) {
            mx = Math.max(mx, x);
        }

        long ans = 0;
        int cntMx = 0, left = 0;
        for (int x : nums) {
            if (x == mx) {
                cntMx++;
            }
            while (cntMx == k) {
                if (nums[left] == mx) {
                    cntMx--;
                }
                left++;
            }
            ans += left;
        }
        return ans;
    }
}

###cpp

class Solution {
public:
    long long countSubarrays(vector<int>& nums, int k) {
        int mx = ranges::max(nums);
        long long ans = 0;
        int cnt_mx = 0, left = 0;
        for (int x : nums) {
            cnt_mx += x == mx;
            while (cnt_mx == k) {
                cnt_mx -= nums[left] == mx;
                left++;
            }
            ans += left;
        }
        return ans;
    }
};

###c

#define MAX(a, b) ((b) > (a) ? (b) : (a))

long long countSubarrays(int* nums, int numsSize, int k) {
    int mx = nums[0];
    for (int i = 1; i < numsSize; i++) {
        mx = MAX(mx, nums[i]);
    }

    long long ans = 0;
    int cnt_mx = 0, left = 0;
    for (int i = 0; i < numsSize; i++) {
        cnt_mx += nums[i] == mx;
        while (cnt_mx == k) {
            cnt_mx -= nums[left] == mx;
            left++;
        }
        ans += left;
    }
    return ans;
}

###go

func countSubarrays(nums []int, k int) (ans int64) {
mx := slices.Max(nums)
cntMx, left := 0, 0
for _, x := range nums {
if x == mx {
cntMx++
}
for cntMx == k {
if nums[left] == mx {
cntMx--
}
left++
}
ans += int64(left)
}
return
}

###js

var countSubarrays = function(nums, k) {
    const mx = Math.max(...nums);
    let ans = 0, cntMx = 0, left = 0;
    for (const x of nums) {
        if (x === mx) {
            cntMx++;
        }
        while (cntMx === k) {
            if (nums[left] === mx) {
                cntMx--;
            }
            left++;
        }
        ans += left;
    }
    return ans;
};

###rust

impl Solution {
    pub fn count_subarrays(nums: Vec<i32>, k: i32) -> i64 {
        let mx = *nums.iter().max().unwrap();
        let mut ans = 0;
        let mut cnt_mx = 0;
        let mut left = 0;
        for &x in &nums {
            if x == mx {
                cnt_mx += 1;
            }
            while cnt_mx == k {
                if nums[left] == mx {
                    cnt_mx -= 1;
                }
                left += 1;
            }
            ans += left;
        }
        ans as _
    }
}

复杂度分析

时间复杂度：$\mathcal{O}(n)$，其中 $n$ 为 $\textit{nums}$ 的长度。虽然写了个二重循环，但是内层循环中对 $\textit{left}$ 加一的总执行次数不会超过 $n$ 次，所以总的时间复杂度为 $\mathcal{O}(n)$。
空间复杂度：$\mathcal{O}(1)$。

思考题

改成子数组的最大值在子数组中至少出现 $k$ 次，要怎么做？（原题是整个数组的最大值，这里是子数组的最大值）

欢迎在评论区分享你的思路/代码。

提示：907. 子数组的最小值之和

分类题单

如何科学刷题？

我的题解精选（已分类）

欢迎关注 B站@灵茶山艾府

普通视图

复杂度分析

思考题

分类题单