leetcode 795. 区间子数组个数_小张刷题日记的博客-爱代码爱编程
好久没更新啦~最近忙着课题呢 研究生生活感觉有点子没意思 多学习总结 热爱生活!!芜湖~!
题目描述:
给你一个整数数组 nums 和两个整数:left 及 right 。找出 nums 中连续、非空且其中最大元素在范围 [left, right] 内的子数组,并返回满足条件的子数组的个数。
生成的测试用例保证结果符合 32-bit 整数范围。
题目解析:
一看到这道题我第一反应就是,单调栈,左数组记录距离自己左边最近的大于自己的数,右数组记录距离自己右边最近的大于等于自己的数,这里为什么左边是大于,右边是大于等于,构造一个半闭半开的区间来进行自动去重,然后计算每个数对于结果的贡献量,即(当前序号减去左数组对应序号)乘上(右数组对应序号减去当前序号),参考代码可能会好理解一点,代码如下:
class Solution {
public:
int numSubarrayBoundedMax(vector<int>& nums, int left, int right) {
vector<int> leftarr(nums.size(),-1);
vector<int> rightarr(nums.size(),nums.size());
stack<int> stkl;
stack<int> stkr;
for(int i = 0 ; i<leftarr.size() ; i++){
if(stkl.empty()){
stkl.push(i);
continue;
}
while(!stkl.empty()&&nums[stkl.top()]<=nums[i]){
stkl.pop();
}
if(!stkl.empty())leftarr[i] = stkl.top();
stkl.push(i);
}
for(int i = rightarr.size()-1 ; i>=0 ; i--){
if(stkr.empty()){
stkr.push(i);
continue;
}
while(!stkr.empty()&&nums[stkr.top()]<nums[i]){
stkr.pop();
}
if(!stkr.empty())rightarr[i] = stkr.top();
stkr.push(i);
}
int res = 0;
for(int i = 0 ; i<nums.size() ; i++){
if(nums[i]<=right&&nums[i]>=left)res += (i-leftarr[i])*(rightarr[i]-i);
}
return res;
}
};
但是时间运行结果不太理想,在看了答案过后突然发现,使用双指针可以解决这个问题。
我把数据分为三类,第一类小于left,第二类在left和right的全闭区间内,第三类大于right。我遍历数组,以当前遍历点为子数组的右区间,记录上一次出现第二类点的位置和上一次出现第三类点的位置,那么子数组的左区间可以在(last3,last2],将last2-last3加在答案中即可,代码如下:
class Solution {
public:
int numSubarrayBoundedMax(vector<int>& nums, int left, int right) {
int last2 = -1 , last1 = -1;
int res = 0;
for(int i = 0 ; i < nums.size() ; i++){
if(nums[i]<=right&&nums[i]>=left){
last1 = i;
}
else if(nums[i]>right){
last1 = -1;
last2 = i;
continue;
}
if(last1!=-1)res += last1-last2;
}
return res;
}
};
执行用时:64 ms, 在所有 C++ 提交中击败了31.52%的用户
内存消耗:51.1 MB, 在所有 C++ 提交中击败了30.37%的用户
目标值为最大值在left和right之间的子数组数,可以转换为最大值小于等于right的子数组数减去最大值小于left的子数组数,一次遍历进行计算,代码如下:
class Solution {
public:
int numSubarrayBoundedMax(vector<int>& nums, int left, int right) {
return cal(nums,right)-cal(nums,left-1);
}
int cal(vector<int>& nums , int num){
int res = 0 , cur = 0 ;
for(int i = 0 ; i<nums.size() ; i++){
cur = nums[i]<=num?cur+1:0;
res += cur;
}
return res;
}
};
执行用时:56 ms, 在所有 C++ 提交中击败了61.03%的用户
内存消耗:51 MB, 在所有 C++ 提交中击败了48.42%的用户
感觉自己coding有进步,自动去重单调栈一次就写出来了,多加油,科研去了!