跳转至

3874. Valid Subarrays With Exactly One Peak 🔒

题目描述

You are given an integer array nums of length n and an integer k.

An index i is a peak if:

  • 0 < i < n - 1
  • nums[i] > nums[i - 1] and nums[i] > nums[i + 1]

A subarray [l, r] is valid if:

  • It contains exactly one peak at index i from nums
  • i - l <= k and r - i <= k

Return an integer denoting the number of valid subarrays in nums.

A subarray is a contiguous non-empty sequence of elements within an array.

 

Example 1:

Input: nums = [1,3,2], k = 1

Output: 4

Explanation:

  • Index i = 1 is a peak because nums[1] = 3 is greater than nums[0] = 1 and nums[2] = 2.
  • Any valid subarray must include index 1, and the distance from the peak to both ends of the subarray must not exceed k = 1.
  • The valid subarrays are [3], [1, 3], [3, 2], and [1, 3, 2], so the answer is 4.

Example 2:

Input: nums = [7,8,9], k = 2

Output: 0

Explanation:

  • There is no index i such that nums[i] is greater than both nums[i - 1] and nums[i + 1].
  • Therefore, the array contains no peak. Thus, the number of valid subarrays is 0.

Example 3:

Input: nums = [4,3,5,1], k = 2

Output: 6

Explanation:

  • Index i = 2 is a peak because nums[2] = 5 is greater than nums[1] = 3 and nums[3] = 1.
  • Any valid subarray must contain this peak, and the distance from the peak to both ends of the subarray must not exceed k = 2.
  • The valid subarrays are [5], [3, 5], [5, 1], [3, 5, 1], [4, 3, 5], and [4, 3, 5, 1], so the answer is 6.

 

Constraints:

  • 1 <= n == nums.length <= 105
  • -105 <= nums[i] <= 105
  • 1 <= k <= n

解法

方法一：模拟

我们首先遍历数组，找到所有的峰值位置，并将它们存储在一个列表 \(\textit{peaks}\) 中。

对于每个峰值位置，我们计算以该峰值为中心，距离不超过 \(k\) 的左右边界。需要注意的是，如果存在多个峰值，我们需要确保计算的子数组不包含其他峰值。然后根据左右边界计算以该峰值为中心的有效子数组数量，并将其累加到答案中。

时间复杂度 \(O(n)\)，空间复杂度 \(O(n)\)。其中 \(n\) 是数组的长度。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
    def validSubarrays(self, nums: list[int], k: int) -> int:
        n = len(nums)
        peaks = []
        for i in range(1, n - 1):
            if nums[i] > nums[i - 1] and nums[i] > nums[i + 1]:
                peaks.append(i)

        ans = 0
        for j, p in enumerate(peaks):
            left_min = max(p - k, 0)
            if j > 0:
                left_min = max(left_min, peaks[j - 1] + 1)

            right_max = min(p + k, n - 1)
            if j < len(peaks) - 1:
                right_max = min(right_max, peaks[j + 1] - 1)

            ans += (p - left_min + 1) * (right_max - p + 1)
        return ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
    public long validSubarrays(int[] nums, int k) {
        int n = nums.length;
        List<Integer> peaks = new ArrayList<>();

        for (int i = 1; i < n - 1; i++) {
            if (nums[i] > nums[i - 1] && nums[i] > nums[i + 1]) {
                peaks.add(i);
            }
        }

        long ans = 0;
        for (int j = 0; j < peaks.size(); j++) {
            int p = peaks.get(j);

            int leftMin = Math.max(p - k, 0);
            if (j > 0) {
                leftMin = Math.max(leftMin, peaks.get(j - 1) + 1);
            }

            int rightMax = Math.min(p + k, n - 1);
            if (j < peaks.size() - 1) {
                rightMax = Math.min(rightMax, peaks.get(j + 1) - 1);
            }

            ans += (long) (p - leftMin + 1) * (rightMax - p + 1);
        }

        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
public:
    long long validSubarrays(vector<int>& nums, int k) {
        int n = nums.size();
        vector<int> peaks;

        for (int i = 1; i < n - 1; ++i) {
            if (nums[i] > nums[i - 1] && nums[i] > nums[i + 1]) {
                peaks.push_back(i);
            }
        }

        long long ans = 0;
        for (int j = 0; j < peaks.size(); ++j) {
            int p = peaks[j];

            int leftMin = max(p - k, 0);
            if (j > 0) {
                leftMin = max(leftMin, peaks[j - 1] + 1);
            }

            int rightMax = min(p + k, n - 1);
            if (j < peaks.size() - 1) {
                rightMax = min(rightMax, peaks[j + 1] - 1);
            }

            ans += 1LL * (p - leftMin + 1) * (rightMax - p + 1);
        }

        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
func validSubarrays(nums []int, k int) int64 {
    n := len(nums)
    peaks := []int{}

    for i := 1; i < n-1; i++ {
        if nums[i] > nums[i-1] && nums[i] > nums[i+1] {
            peaks = append(peaks, i)
        }
    }

    var ans int64
    for j, p := range peaks {
        leftMin := max(p-k, 0)
        if j > 0 {
            leftMin = max(leftMin, peaks[j-1]+1)
        }

        rightMax := min(p+k, n-1)
        if j < len(peaks)-1 {
            rightMax = min(rightMax, peaks[j+1]-1)
        }

        ans += int64(p-leftMin+1) * int64(rightMax-p+1)
    }

    return ans
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
function validSubarrays(nums: number[], k: number): number {
    const n = nums.length;
    const peaks: number[] = [];

    for (let i = 1; i < n - 1; i++) {
        if (nums[i] > nums[i - 1] && nums[i] > nums[i + 1]) {
            peaks.push(i);
        }
    }

    let ans = 0;
    for (let j = 0; j < peaks.length; j++) {
        const p = peaks[j];

        let leftMin = Math.max(p - k, 0);
        if (j > 0) {
            leftMin = Math.max(leftMin, peaks[j - 1] + 1);
        }

        let rightMax = Math.min(p + k, n - 1);
        if (j < peaks.length - 1) {
            rightMax = Math.min(rightMax, peaks[j + 1] - 1);
        }

        ans += (p - leftMin + 1) * (rightMax - p + 1);
    }

    return ans;
}

评论