统计定界子数组的数目

2023-12-25 00:52
文章标签 统计 数组 数目 定界

本文主要是介绍统计定界子数组的数目,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

说在前面

🎈不知道大家对于算法的学习是一个怎样的心态呢?为了面试还是因为兴趣?不管是出于什么原因,算法学习需要持续保持。

题目描述

给你一个整数数组 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和两个整数minKmink,我们需要统计满足以下条件的子数组数量。

  • 子数组中的 最小值 等于 minK 。
  • 子数组中的 最大值 等于 maxK 。

image.png
如上图示例一,我们可以得到两个满足条件的子数组:[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

image.png
我们可以从以下几种情况来分析:

  • 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]

1665933398636.png

- 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,现在是一名前端工程师,有空会刷刷算法题,平时喜欢打羽毛球 🏸 ,平时也喜欢写些东西,既为自己记录 📋,也希望可以对大家有那么一丢丢的帮助,写的不好望多多谅解 🙇,写错的地方望指出,定会认真改进 😊,偶尔也会在自己的公众号『前端也能这么有趣』发一些比较有趣的文章,有兴趣的也可以关注下。在此谢谢大家的支持,我们下文再见 🙌。

这篇关于统计定界子数组的数目的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/533739

相关文章

hdu1496(用hash思想统计数目)

作为一个刚学hash的孩子,感觉这道题目很不错,灵活的运用的数组的下标。 解题步骤:如果用常规方法解,那么时间复杂度为O(n^4),肯定会超时,然后参考了网上的解题方法,将等式分成两个部分,a*x1^2+b*x2^2和c*x3^2+d*x4^2, 各自作为数组的下标,如果两部分相加为0,则满足等式; 代码如下: #include<iostream>#include<algorithm

hdu2241(二分+合并数组)

题意:判断是否存在a+b+c = x,a,b,c分别属于集合A,B,C 如果用暴力会超时,所以这里用到了数组合并,将b,c数组合并成d,d数组存的是b,c数组元素的和,然后对d数组进行二分就可以了 代码如下(附注释): #include<iostream>#include<algorithm>#include<cstring>#include<stack>#include<que

hdu 1166 敌兵布阵(树状数组 or 线段树)

题意是求一个线段的和,在线段上可以进行加减的修改。 树状数组的模板题。 代码: #include <stdio.h>#include <string.h>const int maxn = 50000 + 1;int c[maxn];int n;int lowbit(int x){return x & -x;}void add(int x, int num){while

flume系列之:查看flume系统日志、查看统计flume日志类型、查看flume日志

遍历指定目录下多个文件查找指定内容 服务器系统日志会记录flume相关日志 cat /var/log/messages |grep -i oom 查找系统日志中关于flume的指定日志 import osdef search_string_in_files(directory, search_string):count = 0

hdu4267区间统计

题意:给一些数,有两种操作,一种是在[a,b] 区间内,对(i - a)% k == 0 的加value,另一种操作是询问某个位置的值。 import java.io.BufferedInputStream;import java.io.BufferedReader;import java.io.IOException;import java.io.InputStream;import

hdu4417区间统计

给你一个数列{An},然后有m次查询,每次查询一段区间 [l,r] <= h 的值的个数。 import java.io.BufferedInputStream;import java.io.BufferedReader;import java.io.IOException;import java.io.InputStream;import java.io.InputStreamRead

hdu3333区间统计

题目大意:求一个区间内不重复数字的和,例如1 1 1 3,区间[1,4]的和为4。 import java.io.BufferedInputStream;import java.io.BufferedReader;import java.io.IOException;import java.io.InputStream;import java.io.InputStreamReader;

实例:如何统计当前主机的连接状态和连接数

统计当前主机的连接状态和连接数 在 Linux 中,可使用 ss 命令来查看主机的网络连接状态。以下是统计当前主机连接状态和连接主机数量的具体操作。 1. 统计当前主机的连接状态 使用 ss 命令结合 grep、cut、sort 和 uniq 命令来统计当前主机的 TCP 连接状态。 ss -nta | grep -v '^State' | cut -d " " -f 1 | sort |

C语言:柔性数组

数组定义 柔性数组 err int arr[0] = {0}; // ERROR 柔性数组 // 常见struct Test{int len;char arr[1024];} // 柔性数组struct Test{int len;char arr[0];}struct Test *t;t = malloc(sizeof(Test) + 11);strcpy(t->arr,

C 语言基础之数组

文章目录 什么是数组数组变量的声明多维数组 什么是数组 数组,顾名思义,就是一组数。 假如班上有 30 个同学,让你编程统计每个人的分数,求最高分、最低分、平均分等。如果不知道数组,你只能这样写代码: int ZhangSan_score = 95;int LiSi_score = 90;......int LiuDong_score = 100;int Zhou