package othercode.Stack;

import java.util.LinkedList;

/**
 * 题目描述：
 * 最大值减去最小值小于或等于num的子数组数量
 *
 * 给定数组 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]中的最小值。
 *
 * 题目思路：
 * 暴力求解的时间复杂度为O(N^3),不可取，这里可以实现时间复杂度为O(N)的解法。
 * 有两个重要逻辑：
 * 1、如果子数组arr[i,j]满足条件，则arr[i,j]中的每一个子数组都满足条件。
 * 2、如果子数组arr[i,j]不满足条件，则所有包含arr[i,j]的子数组都不满足条件。
 * 这道题目本质上需要计算每个子数组的最大值与最小值的差，判断是否符合要求。
 * 所以需要设计一个快速获得最大值和最小值的方法。由于子数组中的数字下标是连续的，可以考虑队列和栈之类的结构来实现。
 * 参考leetcode239_maxSlidingWindow“生成窗口最大值数组”，可以用双向队列来实现快速获取最大值和最小值。
 *
 * 过程如下：
 * 1.生成两个双端队列max和min，生成两个整型变量i和j，表示子数组范围，利用res记录满足条件的子数组的数量;
 * 2.令j不断右移，不断更新max和min来判断当前子数组是否满足条件。一旦出现arr[i,j]不满足的情况出现，则j停止向右扩的过程，
 *   此时arr[i,j-1]，arr[i,j-2]，……，arr[i,i]一定均满足条件。满足条件的数量为j-i个，于是令res+=j-i；
 * 3.令i右移一个位置，对max和min进行更新，max和min从原来的arr[i,j]窗口更新成arr[i+1,j]窗口的最大值和最小值结构。重复步骤2。
 *   也就是求所有必须以arr[i+1]作为第一个元素的子数组中，满足条件的数量有多少。
 * 4.根据步骤2和3，依次分别求出，必须以a[0],a[1],a[2].....开头的子数组中满足条件的有多少个，全部累加后得到结果。
 *
 * 上述过程中，所有下标值最多进qmax和qmin一次，出一次。i和j的值也不断增加，不减少。整个过程的时间复杂度为O(N)。
 */
public class subArrNum {
    public static int getSubArrNum(int arr[],int num){
        if(arr == null||arr.length == 0||num < 0)
            return 0;
        LinkedList<Integer> qmax = new LinkedList<>();
        LinkedList<Integer> qmin = new LinkedList<>();
        int res = 0;
        int i = 0;
        int j =0;
        while(i < arr.length){
            while(j < arr.length){
                while (!qmin.isEmpty() && arr[j] <= arr[qmin.peekLast()]) {
                    qmin.pollLast();
                }
                qmin.addLast(j);
                while (!qmax.isEmpty() && arr[j] >= arr[qmax.peekLast()]) {
                    qmax.pollLast();
                }
                qmax.addLast(j);

                if(arr[qmax.peekFirst()] - arr[qmin.peekFirst()] > num)
                    break;
                j++;
            }
            res+= j - i;
            if(qmin.peekFirst() == i){
                qmin.pollFirst();
            }
            if(qmax.peekFirst() == i){
                qmax.pollFirst();
            }
            i++;
        }
        return res;
    }
    public static void main(String[] args){
        int[] arr = {1,2,4,3,2,4,4,5};
        int num = 1;
        int res = getSubArrNum(arr,num);
        System.out.println(res);

    }

}