You are given an integer array nums of length n and an integer k.
An index i is a peak if:
0 < i < n - 1nums[i] > nums[i - 1] and nums[i] > nums[i + 1]A subarray [l, r] is valid if:
i from numsi - l <= k and r - i <= kReturn an integer denoting the number of valid subarrays in nums.
Example 1:
Input: nums = [1,3,2], k = 1
Output: 4
Explanation:
i = 1 is a peak because nums[1] = 3 is greater than nums[0] = 1 and nums[2] = 2.k = 1.[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:
i such that nums[i] is greater than both nums[i - 1] and nums[i + 1].Example 3:
Input: nums = [4,3,5,1], k = 2
Output: 6
Explanation:
i = 2 is a peak because nums[2] = 5 is greater than nums[1] = 3 and nums[3] = 1.k = 2.[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] <= 1051 <= k <= nWe first traverse the array to find all peak positions and store them in a list peaks.
For each peak position, we calculate the left and right boundaries centered at the peak with a distance not exceeding k. Note that if there are multiple peaks, we need to ensure the calculated subarray does not contain other peaks. Then, based on the left and right boundaries, we calculate the number of valid subarrays centered at each peak and accumulate it into the answer.
The time complexity is O(n), and the space complexity is O(n), where n is the length of the array.
Java
C++
Go
TypeScript
Practice Valid Subarrays With Exactly One Peak with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor