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/
原文地址：http://www.cnblogs.com/onlyblues/p/16796515.html
