英文淘宝网站建设,wordpress 内容模板下载失败,视差设计网站,开源软件#达标子数组#
求达标子数组的数量
* 题目#xff1a;给定一个数组#xff0c;求满足子数组中最大值-最小值小于等于某个数的子数组的数量
* 例如[0,1,2,3]中求子数组中最大值-最小值小于等于 2的子数组的数量
* 结果为9,因为满足条件的只有[0,0] [0,1] [0,2] [1,1] [1,2] [1…#达标子数组#
求达标子数组的数量
* 题目给定一个数组求满足子数组中最大值-最小值小于等于某个数的子数组的数量
* 例如[0,1,2,3]中求子数组中最大值-最小值小于等于 2的子数组的数量
* 结果为9,因为满足条件的只有[0,0] [0,1] [0,2] [1,1] [1,2] [1,3] [2,2] [2,3] [3,3]
题目对应的代码如下
首先讨论暴力解这种解法特别容易想就是把所有的子数组进行枚举例如0~0,0~1,0~2,0~3, 0~4...2~2,2~2,2~3,2~4...然后依次找到每个子数组的最大值和最小值根据二者之差判断是否达标如果达标则总的数量加1两层for循环的时间复杂度是O(N^2)面试场没分
重点讨论第二种解法也是本题的重要考察点滑动窗口对于滑动窗口解法来说每个位置最多进一次窗口也最多出一次窗口所以时间复杂度是O(N)这个已经是最好的解法了你不可能所有的位置都没看完就找到所有答案
public class AllLessNumSubArray {/*** 暴力解百分百正确但是面试场上没分*/public static int right(int[] nums, int limit) {if(nums null || nums.length 0 || limit 0) {return 0;}int result 0;for(int i 0; i nums.length; i) {int max nums[i];int min nums[i];for(int j i; j nums.length; j) {max Math.max(max, nums[j]);min Math.min(min, nums[j]);if(max - min limit) break;if(max - min limit) result ;}}return result;}public static int better(int[] nums, int limit) {//不满足基本的条件返回0个if(nums null || nums.length 0 || limit 0) {return 0;}//数组的长度int N nums.length;//创建最大值和最小值窗口使用双端队列LinkedListInteger min new LinkedList();LinkedListInteger max new LinkedList();//L和R都从0开始形成的区间是[L,R]左开右闭int R 0;int L 0;//最终结果统计int result 0;//L,R的边界都是小于N都是不回退的while(L N) {while(R N) {//如果当前最小值窗口中有数字大于要进去的R的位置的数字依次弹出while(!min.isEmpty() nums[min.peekLast()] nums[R]) {min.pollLast();}//R入最小值窗口min.addLast(R);//如果当前最大值窗口中有数字小于要进去的R的位置的数字依次弹出while(!max.isEmpty() nums[max.peekLast()] nums[R]) {max.pollLast();}//R入最小值窗口max.addLast(R);//当前窗口最大值-最小值如果不满足《limit终止//如果满足条件R继续R是以L下标开始第一个不满足条件的if(nums[max.peekFirst()] - nums[min.peekFirst()] limit) {break;} else {R;}}//因为L马上要进行L操作了所以L位置马上过期如果最大值或者最小值窗口的头部是L则弹出头部if(max.peekFirst() L) {max.pollFirst();}if(min.peekFirst() L) {min.pollFirst();}//R是以L为起点的子数组中第一个不满足max-minlimit的节点所以数量加上(R - L)result (R - L);L;}return result;}}
