Count Subarrays With Fixed Bounds

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 \leq nums.length \leq {10}^{5}$
$1 \leq nums[i], minK, maxK \leq {10}^{6}$

解题思路

　　先说说比赛时的做法。先考虑暴力的做法，枚举右端点$i$，从$i$往左找到第一个小于$minK$或大于$maxK$的数，假设这个数的下标为$j$，那么很明显我们要求的子数组必定在$[j+1,i]$内。然后再从$i$往左求后缀最小值和后缀最大值，如果发现枚举到下标$k$时有第一次同时满足后缀最小值等于$minK$和后缀最大值等于$maxK$，那么此时在区间$[j+1,k]$内的下标都可以作为子数组的左端点，因此以$i$为右端点的满足条件的子数组有$k - j$个。这种做法的时间复杂度是$O(n^2)$。

　　接下来看看能不能对枚举的过程进行优化。首先是从右往左找到第一个超出$minK$和$maxK$范围内的数，这个可以开个变量来记录上一个不满足条件的数的下标，这样就不用每次都重新枚举。然后是找后缀最大值最小值，本质就是找到左边值为$minK$和$maxK$的最大下标，这两个下标的最小值就是上面所说的$k$，因此在往后枚举$i$的过程中可以开两个变量来分别记录$minK$和$maxK$的最大下标，这样就不用每次往左重新枚举了。时间复杂度就变成$O(n)$。

　　AC代码如下：

 1 class Solution {
 2 public:
 3     long long countSubarrays(vector<int>& nums, int minK, int maxK) {
 4         long long ret = 0;
 5         for (int i = 0, t = -1, a = -1, b = -1; i < nums.size(); i++) {
 6             if (nums[i] < minK || nums[i] > maxK) {
 7                 t = i;
 8                 a = b = -1;
 9             }
10             else {
11                 if (nums[i] == minK) a = i;
12                 if (nums[i] == maxK) b = i;
13                 if (a != -1 && b != -1) ret += min(a, b) - t;
14             }
15         }
16         return ret;
17     }
18 };

　　下面说一下双指针的做法，当时写的时候没想到双指针怎么做。

　　一样先把不在$minK$和$maxK$范围内的数找出来，这样就可以把数组分成若干段，答案也不可能跨过分界点，不然就不满足数组中最小值为$minK$和最大值为$maxK$，因此分别看每一段就可以了。

　　枚举右端点$i$，在$i$的左边找到一个$j$，可以发现$j$离$i$越远，范围就会越大，即更有可能包含更多的$minK$和$maxK$。因此$j$可以定义为最靠近$i$的位置，使得区间$[j, i]$内至少包含一个$minK$和$maxK$，这样$j$到分界点这些位置与右端点$i$都是可以构成满足要求的子数组，而$j+1$到$i$这些位置都是不可以构成满足要求的子数组。

　　当$i$往右走时$j$也只会往右走而不会往左走，因此可以用双指针。这是因为如果$i$往右走到$i'$，$i'$对应的$j'$是在$j$的左边（即$j$往左走），那么由于区间$[j, i]$内至少存在一个$minK$和$maxK$，因此区间$[j,i']$内也必定至少存在一个$minK$和$maxK$，这样$[j, i']$也是满足条件且比$j'$更靠近$i'$，这就证明指针$j$不会往左走。

　　AC代码如下：

 1 class Solution {
 2 public:
 3     long long countSubarrays(vector<int>& nums, int minK, int maxK) {
 4         long long ret = 0;
 5         int smin = 0, smax = 0;
 6         for (int i = 0, j = 0, last = 0; i < nums.size(); i++) {
 7             if (nums[i] < minK || nums[i] > maxK) {
 8                 last = j = i + 1;
 9                 smin = smax = 0;
10             }
11             else {
12                 if (nums[i] == minK) smin++;
13                 if (nums[i] == maxK) smax++;
14                 while (j < i) {
15                     if (nums[j] == minK) smin--;
16                     if (nums[j] == maxK) smax--;
17                     if (!smin || !smax) {
18                         if (nums[j] == minK) smin++;
19                         if (nums[j] == maxK) smax++;
20                         break;
21                     }
22                     j++;
23                 }
24                 if (smin && smax) ret += j - last + 1;
25             }
26         }
27         return ret;
28     }
29 };

参考资料

　　力扣第315场周赛：https://www.bilibili.com/video/BV1Yg411a7NM/