跳转至

3874. 具有恰好一个峰值的有效子数组 🔒

题目描述

给定一个长度为 n 的整数数组 nums 和一个整数 k。

下标 i 是 峰值 的条件为：

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

一个子数组 [l, r] 是 有效 的条件是：

  • 它 恰好有一个 nums 中下标 i 处的峰值
  • i - l <= k 且 r - i <= k

返回一个整数，表示 nums 中 有效子数组 的数量。

子数组 是数组中的连续 非空 元素序列。

 

示例 1：

输入：nums = [1,3,2], k = 1

输出：4

解释：

  • 下标 i = 1 是一个峰值，因为 nums[1] = 3 大于 nums[0] = 1 和 nums[2] = 2。
  • 任何有效的子数组必须包含下标 1，且子数组两端到峰值的距离不得超过 k = 1。
  • 有效的子数组是 [3]，[1, 3]，[3, 2] 和 [1, 3, 2]，所以答案是 4。

示例 2：

输入：nums = [7,8,9], k = 2

输出：0

解释：

  • 没有下标 i 使得 nums[i] 同时比 nums[i - 1] 和 nums[i + 1] 更大。
  • 因此，该数组中没有峰值。所以，有效子数组的数量为 0。

示例 3：

输入：nums = [4,3,5,1], k = 2

输出：6

解释：

  • 下标 i = 2 是一个峰值，因为 nums[2] = 5 大于 nums[1] = 3 和 nums[3] = 1。
  • 任何有效的子数组都必须包含这个峰值，并且峰值到子数组两端的距离不得超过 k = 2。
  • 合法子数组是 [5]，[3, 5]，[5, 1]，[3, 5, 1]，[4, 3, 5] 和 [4, 3, 5, 1]，所以答案是 6。

 

提示：

  • 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;
}

评论