算法题-最大值减去最小值小于或等于 num 的子数组数量

xiaoxiao2021-02-28  11

【题目】 给定数组 arr 和整数 num,共返回有多少个子数组满足如下情况: max(arr[i..j]) - min(arr[i..j]) <= num max(arr[i..j])表示子数组 arr[i..j]中的最大值,min(arr[i..j])表示子数组 arr[i..j]中的最 小值。 【要求】 如果数组长度为 N,请实现时间复杂度为 O(N)的解法。 import java.util.LinkedList; /** * Created by 糖糖 on 2017/8/2. */ public class getnum33 { public static int getnum(int arr[],int num){ LinkedList<Integer> qmin=new LinkedList<>(); LinkedList<Integer> qmax=new LinkedList<>(); int res=0; int i=0; int j=0; while (i<arr.length){ while (j<arr.length){ while (!qmin.isEmpty() && arr[qmin.peekLast()]>= arr[j]) qmin.pollLast(); qmin.addLast(j); while (!qmax.isEmpty() && arr[qmax.peekLast()]<=arr[j]) qmax.pollLast(); qmax.addLast(j); if(arr[qmax.peekFirst()]-arr[qmin.peekFirst()]>num) break; j++; } if(i==qmin.peekFirst()) qmin.pollFirst(); if(i==qmax.peekFirst()) qmax.pollFirst(); res+=j-i; i++; } return res; } public static void main(String args[]){ int arr[]={3,4,5,1,7,8}; System.out.print(getnum(arr,2)); } }
转载请注明原文地址: https://www.6miu.com/read-1100119.html

最新回复(0)