首页 > 其他分享 >LeetCode/区间子数组个数

LeetCode/区间子数组个数

时间:2023-06-12 18:44:46浏览次数:43  
标签:arr right nums int 个数 数组 monoStack LeetCode left

给你一个整数数组 nums 和两个整数:left 及 right
找出 nums 中连续、非空且其中最大元素在范围 [left, right] 内的子数组,并返回满足条件的子数组的个数

1. 遍历区间右端点 + 同时记录满足条件的左边点位

数组中不能含有大于 right的元素,
且至少含有一个处于 [left,right]区间的元素
所以遍历时只需记录最近不满足条件的点位
和最近满足条件的点位即可,可以将其之间的元素,作为新增右端点的区间左端点

class Solution {
public:
    int numSubarrayBoundedMax(vector<int>& nums, int left, int right) {
        int res = 0, last2 = -1, last1 = -1;
        for (int i = 0; i < nums.size(); i++) { //直接遍历维护右端点
            if (nums[i] >= left && nums[i] <= right) 
                last1 = i; //更新记录满足条件的最远点1
            else if (nums[i] > right) {
                last2 = i; //更新记录不满足条件的最远点2
                last1 = -1;  //当前数为点2则不存在区间满足条件
            }
            //
            if (last1 != -1) 
                res += last1 - last2;
        }
        return res;
    }
};

2. 转化问题

所有元素小于等于right数组 - 所有元素小于left数组

class Solution {
public:
    int numSubarrayBoundedMax(vector<int>& nums, int left, int right) {
        return count(nums, right) - count(nums, left - 1);
    }

    int count(vector<int>& nums, int lower) {
        int res = 0, cur = 0; //cur记录连续满足条件的长度
        for (auto x : nums) { //以x为右端点
            cur = x <= lower ? cur + 1 : 0; //满足条件增加,否则重置
            res += cur;
        }
        return res;
    }
};

3,. 区间单调栈板子

class Solution {
public:
    int numSubarrayBoundedMax(vector<int>& arr, int l, int r) {
        int n = arr.size();
        vector<int> monoStack; //单调栈
        vector<int> left(n), right(n);//左右边界,表示以i最大值的左右边界
        for (int i = 0; i < n; i++) {//从左往右找左边更大值
            while (!monoStack.empty() && arr[i] >= arr[monoStack.back()]) {//把更大的值挤出来,相等的视为更大(即最右边值统御左边相同元素)
                monoStack.pop_back();
            }
            left[i] = i - (monoStack.empty() ? -1 : monoStack.back()); //左区间长度
            monoStack.emplace_back(i);//放入坐标
        }
        monoStack.clear();
        for (int i = n - 1; i >= 0; i--) { //从右往左找右边更大值
            while (!monoStack.empty() && arr[i] > arr[monoStack.back()]) {
                monoStack.pop_back();
            }
            right[i] = (monoStack.empty() ? n : monoStack.back()) - i; //右区间长度
            monoStack.emplace_back(i);
        }
        int ans = 0;
        for (int i = 0; i < n; i++){  //计算每个值的贡献
            if(arr[i]>r||arr[i]<l) continue;
            ans = ans + left[i] * right[i]; 
        }
        return ans;
    }
};

标签:arr,right,nums,int,个数,数组,monoStack,LeetCode,left
From: https://www.cnblogs.com/929code/p/17475844.html

相关文章

  • 315. 计算右侧小于当前元素的个数
    labuladong题解难度困难987给你一个整数数组 nums ,按要求返回一个新数组 counts 。数组 counts 有该性质: counts[i] 的值是  nums[i] 右侧小于 nums[i] 的元素的数量。 示例1:输入:nums=[5,2,6,1]输出:[2,1,1,0]解释:5的右侧有2个更小的元素(2和......
  • 80 二维数组
    packagecom.fqs.test;importjava.util.Random;publicclasshello{publicstaticvoidmain(String[]args){//定义数组int[][]arr3={{1,2,3},{4,5,6,7,8}};//获取元素System.out.prin......
  • Arrays ——操作数组的工具类
    Arrays——操作数组的工具类方法名说明publicstaticStringtoString(数组)把数组拼接成一个字符串publicstaticintbinarySearch(数组,查找的元素)二分法查找元素publicstaticint[]copyof(原数组,新数组长度)拷贝数组publicstaticint[]copyofRange(......
  • HDU 2838 Cow Sorting(树状数组)
    题意:首先每次只能交换相邻的两头牛,并且最后要求升序排列,所以最后整个序列的逆序是0,每次交换只可以消除1个逆序。(令a[i]的逆序是从1到i-1比它大的数的个数。)思路:对于某个数,要把它变成有序的,那么很容易可以推算出公式就是它自身的逆序数乘自身的值再加上它的逆序数的和,自己算算看看。......
  • HDU 1394 Minimum Inversion Number(树状数组)
    题意:有一个n个整数的排列,这n个整数就是0,1,2,3...n-1这n个数(但不一定按这个顺序给出)。现在先计算一下初始排列的逆序数,然后把第一个元素a1放到an后面去,形成新排列a2a3a4...ana1,然后再求这个排列的逆序数。继续执行类似操作(一共要执行n-1次)直到产生排列ana1a2...an-1为止。......
  • HDU 3743 Frosh Week(树状数组+离散化)
    题意和思路:和POJ2299几乎一样...离散化+树状数组#include<cstdio>#include<queue>#include<cstring>#include<iostream>#include<cstdlib>#include<algorithm>#include<vector>#include<map>#include<string>#includ......
  • POJ 2352 HDU1541 Stars(树状数组)
    题意:二维平面给定n个点的坐标,然后要你输出每个点的“等级“。每个点的等级是它的左下放的点个数(包括正下放和正左方的点)。即要你输出对于每个点(x,y)来说,有多少点的坐标(xi,yi)满足xi<=x且yi<=y。思路:题目给出的坐标中已经是按y升序排列,那么其实只用考虑x轴,那么显然就是在前面的......
  • HDU 1556 Color the ball(树状数组区间更新)
    题意:中文题思路:一道区间更新,单点查询的裸题,用线段树做更好,因为还没看到所以这里用树状数组做。树状数组标记区间的方法很特别,比如给区间[a,b]内的气球涂颜色时,我们add(a,1),add(b+1,-1),单点查询的时候sum(x)就是x这个气球被涂色的总次数。建议先在纸上自己试一下看看,有点抽象,可以这......
  • 求一个不重复的数组
    packagecom.fqs.test;importjava.util.Random;publicclasshello{publicstaticvoidmain(String[]args){intweishu=6;int[]arr1=getNo(weishu);for(inti=0;i<weishu;i++){System.out.println("ar......
  • [leetcode每日一题]6.12
    1483. 树节点的第K个祖先提示困难150相关企业给你一棵树,树上有 n 个节点,按从 0 到 n-1 编号。树以父节点数组的形式给出,其中 parent[i] 是节点 i 的父节点。树的根节点是编号为 0 的节点。树节点的第 k 个祖先节点是从该节点到根节点路径上的第 k 个节点。实现......