题目 #
You are given an integer array nums and two integers minK and maxK.
A fixed-bound subarray of nums is a subarray that satisfies the following conditions:
- The minimum value in the subarray is equal to minK.
- The maximum value in the subarray is equal to maxK.
Return the number of fixed-bound subarrays.
A subarray is a contiguous part of an array.
Example 1:
Input: nums = [1,3,5,2,7,5], minK = 1, maxK = 5
Output: 2
Explanation: The fixed-bound subarrays are [1,3,5] and [1,3,5,2].
Example 2:
Input: nums = [1,1,1,1], minK = 1, maxK = 1
Output: 10
Explanation: Every subarray of nums is a fixed-bound subarray. There are 10 possible subarrays.
Constraints:
- $2 <= nums.length <= 10^5$
- $1 <= nums[i], minK, maxK <= 10^6$
思路1 分析性质一次遍历 #
分析 #
- 定界子数组里面只有minK和maxK之间的数,并且要求包含minK和maxK
- 可以找一个起点和终点,如果中间包含minK和maxK就代表一个满足条件的子数组,起点到第一个minK或maxK之间的每个点都可以和终点组成一个子数组
- 如果出现一个大于maxK或小于minK的,就将起点设置成下一个
- minK和maxK所在索引都大于起点,就可以计算子数组数量
代码实现 #
1func min(a, b int) int {
2 if a < b {
3 return a
4 }
5 return b
6}
7
8func max(a, b int) int {
9 if a > b {
10 return a
11 }
12 return b
13}
14
15func countSubarrays(nums []int, minK int, maxK int) int64 {
16 s, minI, maxI := -1, -1, -1
17 var result int64 = 0
18 for e, v := range nums {
19 if v < minK || v > maxK {
20 s = e // 子数组不包含s
21 continue
22 }
23 if v == minK {
24 minI = e
25 }
26 if v == maxK {
27 maxI = e
28 }
29 // 1 2 3 4 5
30 // s i e
31 // minI或maxI有一个小于s就不用计算,也就是+0
32 // 都大于s,就是起点到较小的那个之间的数量都满足要求
33 result += int64(max(min(minI, maxI)-s, 0))
34 }
35 return result
36}