即 max(arr[i.....j])-min(arr[i...j])<=num所有子串个数
如: arr=[1,2,3,11,2,3] num=3 ;则满足条件的所有子串数组：[1]、[2]、[3]、[11]、[2]、[3]、[1,2]、[2,3]、[2,3]、[1,2,3]
public class MaxMinArrayNum { public static void main(String[] args){ int[] arr = {1,2,3,11,2,3}; int res = maxmin_num(arr, 3); System.out.print(res); } //arr：数组 num:最大不超过的数值 public static int maxmin_num(int[] arr, int num){ if(arr == null || num <1){ return 0; } int i = 0; int j = 0; //记录结果 int res = 0; //定义两个双端队列，分别存储数组子串的最大值 LinkedList<Integer> min_q = new LinkedList<>(); LinkedList<Integer> max_q = new LinkedList<>(); while(i < arr.length){ while(j<arr.length){ while(!max_q.isEmpty() && arr[max_q.peekLast()]<=arr[j]){ max_q.pollLast(); } max_q.addLast(j); while(!min_q.isEmpty() && arr[min_q.peekLast()]>=arr[j]){ min_q.pollLast(); } min_q.addLast(j); if(arr[max_q.peekFirst()] - arr[min_q.peekFirst()] > num){ break; } j++; } res += (j-i); if(max_q.peekFirst() == i){ max_q.pollFirst(); } if(min_q.peekFirst() == i){ min_q.pollFirst(); } i++; } return res; } }
