双指针+暴力+思维(优化)
思路
见: https://leetcode-cn.com/problems/number-of-subarrays-with-bounded-maximum/solution/shuang-zhi-zhen-by-bao-ling-zhi-zi-c3q4/
这个优化后的代码确实聪明!
暴力不能过代码(43/46)
class Solution {
public:
int numSubarrayBoundedMax(vector<int>& nums, int left, int right) {
int l=0,sum=0,n=nums.size();
for(int i=0;i<n;i++)
{
if(nums[i]>=left&&nums[i]<=right)
sum++;
if(nums[i]>right)
{
l=i+1;
continue;
}
int max_num=nums[i];
for(int j=i-1;j>=l;j--)
{
max_num=max(nums[j],max_num);
if(max_num>=left&&max_num<=right)
sum++;
if(max_num>right)
break;
}
}
return sum;
}
};
经过多思考优化后的AC代码
class Solution {
public:
int numSubarrayBoundedMax(vector<int>& nums, int left, int right) {
int l=0,sum=0,n=nums.size(),flag=-1;
for(int i=0;i<n;i++)
{
if(nums[i]>=left&&nums[i]<=right)
flag=i;
if(nums[i]>right)
{
l=i+1;
flag=-1;
continue;
}
if(flag!=-1)
sum+=(flag-l+1);
}
return sum;
}
};