栈和队列——最大值减去最小值小于或等于num的子数组数量

r囧r小猫 2022-06-06 08:15 105阅读 0赞

【题目】  
　　给定数组arr和整数num，共返回有多少个子数组满足如下情况：  
　　max(arr\[i…j\]) - max(arr\[i…j\]) <= num  
　　max(arr\[i…j\])表示子数组arr\[i…j\]中的最大值，min(arr\[i…j\])表示子数组arr\[i…j\])中的最小值

普通的逻辑解法就是，找到arr的所有子数组，然后对每一个子数组做遍历找到其中的最小值和最大值，然后看看这个子数组是否满足条件，统计所有满足的子数组数量即可。这种逻辑比较简单，这里不做解释，下面的做法实现时间复杂度和空间复杂度都是O(N)

【代码实现】

import java.util.*;
    
    class test{
        public static int getNum(int[] arr,int num){
            if(arr==null || arr.length==0){
                return 0;
            }
            LinkedList<Integer> qmin = new LinkedList<Integer>();
            LinkedList<Integer> qmax = new LinkedList<Integer>();
            int i = 0;
            int j = 0;
            int res = 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(qmin.peekFirst()==i){
                    qmin.pollFirst();
                }
                if(qmax.peekFirst()==i){
                    qmax.pollFirst();
                }
                res += j - i;aaaaaaaaaaa
                i++;
            }
            return res;
        }
    
        public static void main(String[] args){
            int[] arr = new int[]{
       3,10,4,13,16,7};
            int res = getNum(arr,7);
            System.out.println(res);
        }
    }