说在前面
🎈不知道大家对于算法的学习是一个怎样的心态呢?为了面试还是因为兴趣?不管是出于什么原因,算法学习需要持续保持。
题目描述
给你一个整数数组 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 <= 10^5
- 1 <= nums[i], minK, maxK <= 10^6
思路分析
首先我们要先理解一下题目的意思,题目会给我们一个数组nums
和两个整数minK
和mink
,我们需要统计满足以下条件的子数组数量。
- 子数组中的 最小值 等于 minK 。
- 子数组中的 最大值 等于 maxK 。
如上图示例一,我们可以得到两个满足条件的子数组:[1,3,5] 和 [1,3,5,2] 。
首先我们应该要确认几个点:
- 1、子数组的大区间划分
因为子数组中的最大值和最小值需要分别满足:最小值 等于 minK、最大值 等于 maxK,所以我们可以通过这个条件划分每个可能存在子数组的大区间,确定每一个区间的左端点。
- 2、遍历记录最大值和最小值的位置情况
遇到与最大值和最小值相等的数时,我们需要更新其下标。
- 3、根据最小值和最大值下标位置计算存在子数组数量
我们可以看下这个例子:nums = [2,1,5,2,3,5,4,7,2], minK = 2, maxK = 5
我们可以从以下几种情况来分析:
- 1、遍历到下标1时
此时维护的最小值下标minInd = 0
,并未遍历到最大值,其下标为初始值maxInd = -1
,此时区间的左端点为0(从当前位置往左遍历,第一个满足大于等于minK且小于等于maxK的数的下标),此时的左端点与当前区间中间的子数组数目应该为0。
- Math.max(0,Math.min(minInd,maxInd) - l + 1); = Math.max(0,Math.min(0,-1) - 0 + 1); = Math.max(0,-1 - 0 + 1) = 0;
- 2、遍历到下标2时
此时维护的最小值下标minInd = 0
,最大值下标maxInd = 2
,此时区间的左端点为0(从当前位置往左遍历,第一个满足大于等于minK且小于等于maxK的数的下标),此时的左端点与当前区间中间的子数组数目应该为1。
- Math.max(0,Math.min(minInd,maxInd) - l + 1); = Math.max(0,Math.min(0,2) - 0 + 1); = Math.max(0,0 - 0 + 1) = 1;
- 3、遍历到下标3时
此时遇到了新的最小值minK,所以需要更新最小值小标位置,此时维护的最小值下标minInd = 3
,最大值下标maxInd = 2
,区间的左端点为0,此时左端点与当前区间中间的子数组数目应该为3(不考虑前面重复的),如下图:分别为[5,2]、[1,5,2]、[2,1,5,2]
- Math.max(0,Math.min(minInd,maxInd) - l + 1); = Math.max(0,Math.min(3,2) - 0 + 1); = Math.max(0,2 - 0 + 1) = 3;
- 4、遍历到下标7时
下标7位置的值为7,它比最大值要大,所以当前位置不可以构成子数组,我们需要更新区间的左端点,新的左端点应该为下一个满足条件的下标。
if(maxK < nums[i] || minK > nums[i]) l = i + 1;
完整AC代码如下:
AC代码
/** * @param {number[]} nums * @param {number} minK * @param {number} maxK * @return {number} */ var countSubarrays = function(nums, minK, maxK) { let l = 0,r = 0,minInd = -1,maxInd = -1,res = 0; for(let i = 0; i < nums.length; i++){ if(nums[i] == minK) minInd = i; if(nums[i] == maxK) maxInd = i; if(maxK < nums[i] || minK > nums[i]) l = i + 1; res += Math.max(0,Math.min(minInd,maxInd) - l + 1); } return res; };
公众号
关注公众号『前端也能这么有趣
』,获取更多有趣内容。
说在后面
🎉 这里是 JYeontu,现在是一名前端工程师,有空会刷刷算法题,平时喜欢打羽毛球 🏸 ,平时也喜欢写些东西,既为自己记录 📋,也希望可以对大家有那么一丢丢的帮助,写的不好望多多谅解 🙇,写错的地方望指出,定会认真改进 😊,偶尔也会在自己的公众号『
前端也能这么有趣
』发一些比较有趣的文章,有兴趣的也可以关注下。在此谢谢大家的支持,我们下文再见 🙌。