题目
给你一个整数数组 nums 和两个整数 minK 以及 maxK 。
nums 的定界子数组是满足下述条件的一个子数组：
子数组中的 最小值 等于 minK 。
子数组中的 最大值 等于 maxK 。
返回定界子数组的数目。
子数组是数组中的一个连续部分。
示例 1：
输入：nums = [1,3,5,2,7,5], minK = 1, maxK = 5
输出：2
解释：定界子数组是 [1,3,5] 和 [1,3,5,2] 。
示例 2：
输入：nums = [1,1,1,1], minK = 1, maxK = 1
输出：10
解释：nums 的每个子数组都是一个定界子数组。共有 10 个子数组。
参数范围：
2 <= nums.length <= 105
1 <= nums[i], minK, maxK <= 106
分析
时间复杂度: O(n) 枚举每个子数组的终点，求左边界的范围。假定i是右边界。
| iMinMin | 是从nums[0,i]中从右向左第一个小于minK的下标 |
| iMaxMax | 是从nums[0,i]中从右向左第一个大于maxK的下标 |
| iEndMin | 是从nums[0,i]中从右向左第一个等于minK的下标 |
| iEndMax | 是从nums[0,i]中从右向左第一个等于maxK的下标 |
显然left > max(iMinMin ,iMaxMax) 否则最小值更小或最大值更大
left <= min(iEndMin,iEndMax) 否则不存在minK或maxK。
代码
核心代码
class Solution { public: long long countSubarrays(vector<int>& nums, int minK, int maxK) { int iMinMin = -1, iMaxMax = -1; int iEndMin = -1, iEndMax = -1; long long llRet = 0; for (int i = 0; i < nums.size(); i++) { const auto& n = nums[i]; if (n > maxK) { iMaxMax = i; } if (n < minK) { iMinMin = i; } if (n == maxK) { iEndMax = i; } if (n == minK) { iEndMin = i; } const int cur = min(iEndMin, iEndMax) - max(iMinMin, iMaxMax); if (cur > 0) { llRet += cur; } } return llRet; } };
测试用例
template<class T> void Assert(const T& t1, const T& t2) { assert(t1 == t2); } template<class T> void Assert(const vector<T>& v1, const vector<T>& v2) { if (v1.size() != v2.size()) { assert(false); return; } for (int i = 0; i < v1.size(); i++) { Assert(v1[i], v2[i]); } } int main() { vector<int> nums; int minK, maxK; { Solution sln; nums = { 1, 3, 5, 2, 7, 5 }, minK = 1, maxK = 5; auto res = sln.countSubarrays(nums, minK, maxK); Assert(2LL, res); } { Solution sln; nums = { 1, 1, 1, 1 }, minK = 1, maxK = 1; auto res = sln.countSubarrays(nums, minK, maxK); Assert(10LL, res); } }
2023年3月版
class Solution { public: long long countSubarrays(const vector<int>& nums, const int minK, const int maxK) { int iInvalidIndex = -1; int iMinIndex = -1; int iMaxIndex = -1; long long llRet = 0; for (int i = 0; i < nums.size(); i++) { if (minK == nums[i]) { iMinIndex = i; } if (maxK == nums[i]) { iMaxIndex = i; } if ((nums[i] > maxK) || (nums[i] < minK)) { iInvalidIndex = i; } int iCur = min(iMinIndex, iMaxIndex) - iInvalidIndex; if (iCur > 0) { llRet += iCur; } } return llRet; } };
扩展阅读
视频课程
有效学习：明确的目标 及时的反馈 拉伸区（难度合适），可以先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。
https://edu.csdn.net/course/detail/38771
如何你想快
速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176
相关下载
想高屋建瓴的学习算法，请下载《喜缺全书算法册》doc版
https://download.csdn.net/download/he_zhidan/88348653
测试环境
操作系统：win7 开发环境： VS2019 C++17
或者 操作系统：win10 开发环境： VS2022 C++17
如无特殊说明，本算法用C++ 实现。
