栈和队列栈和队列算法

1，设计一个具有getMin功能的栈，概念：在实现基本的栈的功能上，再实现返回栈中的最小元素的操作。
要求：pop、push、getMin的时间复杂度都是O(1)。设计的栈类型可以使用现成的栈结构。

思路：在设计上我们使用两个栈，一个栈用来保存当前的元素，其功能和一个正常的一样，记为stackMin。具体实现方式如下：
假设当前数据为newNum，先将其压入stackData栈，然后判断stackMin是否为空。如果为空，则newNum也压入stackMin；如果不为空，则比较newNum和stackMin的栈顶元素中哪一个更小，如果newNum更小或者相等，则newNum也压入stackMin；如果stackMin中栈顶元素小，则把stackMin元素重复压入stackMin，即在栈顶元素上再压入一个栈顶元素，举例，stackData栈依次压入3、4、5、1、2、1，在这个过程中
stackData栈从栈底到栈顶依次是3、4、5、1、2、1。stackMin栈依次是3、3、3、1、1、1。
弹出数据规则：弹出的数据记为value，弹出stackMin中的栈顶；返回value。代码如下：

public static class MyStack2 {
    private Stack<Integer> stackData;
    private Stack<Integer> stackMin;

    public MyStack2() {
        stackData = new Stack<Integer>();
        stackMin = new Stack<Integer>();
    }

    public void push(int newNum) {
        if (stackMin.isEmpty()) {
            stackMin.push(newNum);
        } else if (newNum < this.getmin()) {
            this.stackMin.push(newNum);
        } else {
            int newMin = this.stackMin.peek();
            this.stackMin.push(newMin);
        }
        this.stackData.push(newNum);
    }

    public int pop() {
        if (this.stackData.isEmpty()) {
            throw new RuntimeException("Your stack is empty.");
        }
        this.stackMin.pop();
        return this.stackData.pop();
    }

    public int getmin() {
        if (this.stackMin.isEmpty()) {
            throw new RuntimeException("Your stack is empty.");
        }
        return this.stackMin.peek();
    }
}

如上所示。
2，题目：由两个栈组成的队列，用两个栈实现队列，支持队列的基本操作
根据栈和队列的特点，我们可以用两个栈，把顺序反过来实现类似队列的操作。具体上是一个栈作为压入栈，在压入的时候只往这个栈中压入，记为stackPush，另一个栈只作为弹出栈，在弹出的时候只从这个栈弹出，记为stackPop。
因为数据压入栈的时候，是先进后出的，那么只要把stackPush的数据再压入stackPop中，顺序就变回来了。
操作过程中要注意以下几点：
1，stackPush栈要往stackPop压入数据，那么必须一次性把stackPush中的数据全部压入。
2，stackPop栈不为空，stackPush不能向stackPop栈压入元素。

public static class TwoStacksQueue {
    public Stack<Integer> stackPush;
    public Stack<Integer> stackPop;

    public TwoStacksQueue() {
        stackPush = new Stack<Integer>();
        stackPop = new Stack<Integer>();
    }

    public void add(int pushInt) {
        stackPush.push(pushInt);
    }

    public int poll() {
        if (stackPop.empty() && stackPush.empty()) {
            throw new RuntimeException("Queue is empty!");
        } else if (stackPop.empty()) {
            while (!stackPush.empty()) {
                stackPop.push(stackPush.pop());
            }
        }
        return stackPop.pop();
    }

    public int peek() {
        if (stackPop.empty() && stackPush.empty()) {
            throw new RuntimeException("Queue is empty!");
        } else if (stackPop.empty()) {
            while (!stackPush.empty()) {
                stackPop.push(stackPush.pop());
            }
        }
        return stackPop.peek();
    }
}

代码如上。
3,使用递归函数和栈操作逆序一个栈。题目：一个栈依次压入1、2、3、4、5。那么从栈顶到栈底分别为5、4、3、2、1。也就是实现栈中元素的逆序，但是只能用递归函数，不能使用其他数据结构。
考察递归函数和栈的操作，设计两个递归函数。
递归函数一：将栈stack的栈底元素返回并移除。
设计一个getAndRemoveLastElement方法。

public static int getAndRemoveLastElement(Stack<Integer> stack) {
    int result = stack.pop();
    if (stack.isEmpty()) {
        return result;
    } else {
        int last = getAndRemoveLastElement(stack);
        stack.push(result);
        return last;
    }
}

代码如上。
递归函数二：逆序一个栈，设计reverse方法，该方法用到了上面提到的getAndRemoveLast方法。

public static void reverse(Stack<Integer> stack) {
    if (stack.isEmpty()) {
        return;
    }
    int i = getAndRemoveLastElement(stack);
    reverse(stack);
    stack.push(i);
}

代码如上。
4，猫狗队列，题目：实现一种猫狗队列的结构，要求如下：
1，add方法可将cat类或dog类的实例放入队列中。
2，pollAll方法可以将队列所有的实例按照进队列的先后顺序依次弹出。
3，pollDog方法可以将队列中的dog类的实例按照进队列的顺序依次弹出。
4，pollCat方法，将队列cat类的实例按照进队列的顺序依次弹出。
5，isEmpty方法检查队列中是否还有dog或者cat的实例。
6，isDogEmpty方法检查队列中是否有dog类的实例。
7，isCatEmpty方法检测队列中是否有cat类的实例。
本题考查实现特殊数据结构的能力以及针对特殊功能的算法设计能力。
代码如下：
pet类

public static class Pet {
    private String type;

    public Pet(String type) {
        this.type = type;
    }

    public String getPetType() {
        return this.type;
    }
}

dog和cat类

public static class Dog extends Pet {
    public Dog() {
        super("dog");
    }
}

public static class Cat extends Pet {
    public Cat() {
        super("cat");
    }
}

主代码：

public static class PetEnterQueue {
    private Pet pet;
    private long count;

    public PetEnterQueue(Pet pet, long count) {
        this.pet = pet;
        this.count = count;
    }

    public Pet getPet() {
        return this.pet;
    }

    public long getCount() {
        return this.count;
    }

    public String getEnterPetType() {
        return this.pet.getPetType();
    }
}

public static class DogCatQueue {
    private Queue<PetEnterQueue> dogQ;
    private Queue<PetEnterQueue> catQ;
    private long count;

    public DogCatQueue() {
        this.dogQ = new LinkedList<PetEnterQueue>();
        this.catQ = new LinkedList<PetEnterQueue>();
        this.count = 0;
    }

    public void add(Pet pet) {
        if (pet.getPetType().equals("dog")) {
            this.dogQ.add(new PetEnterQueue(pet, this.count++));
        } else if (pet.getPetType().equals("cat")) {
            this.catQ.add(new PetEnterQueue(pet, this.count++));
        } else {
            throw new RuntimeException("err, not dog or cat");
        }
    }

    public Pet pollAll() {
        if (!this.dogQ.isEmpty() && !this.catQ.isEmpty()) {
            if (this.dogQ.peek().getCount() < this.catQ.peek().getCount()) {
                return this.dogQ.poll().getPet();
            } else {
                return this.catQ.poll().getPet();
            }
        } else if (!this.dogQ.isEmpty()) {
            return this.dogQ.poll().getPet();
        } else if (!this.catQ.isEmpty()) {
            return this.catQ.poll().getPet();
        } else {
            throw new RuntimeException("err, queue is empty!");
        }
    }

    public Dog pollDog() {
        if (!this.isDogQueueEmpty()) {
            return (Dog) this.dogQ.poll().getPet();
        } else {
            throw new RuntimeException("Dog queue is empty!");
        }
    }

    public Cat pollCat() {
        if (!this.isCatQueueEmpty()) {
            return (Cat) this.catQ.poll().getPet();
        } else
            throw new RuntimeException("Cat queue is empty!");
    }

    public boolean isEmpty() {
        return this.dogQ.isEmpty() && this.catQ.isEmpty();
    }

    public boolean isDogQueueEmpty() {
        return this.dogQ.isEmpty();
    }

    public boolean isCatQueueEmpty() {
        return this.catQ.isEmpty();
    }

}

5，用一个栈实现另一个栈的排序
题目：一个栈中元素的类型为整型，现在想将该栈从栈顶到栈底从大到小排序，只许申请一个栈，可以申请新的变量，但不能额外的数据结构，如何完成排序？
思路：将要排序的栈记为stack，申请的辅助栈记为help，在stack上执行pop操作，弹出的元素记为cur。
1，如果cur小于或等于help栈的栈顶元素，则将cur直接压入help。
2，如果cur大于help的栈顶元素，则将help的元素逐一弹出，逐一压入stack，直到cur小于或等于help的栈顶元素，再将cur压入help。
一直执行以上操作，直到stack栈中的元素全部压入了help，最后将help中所有的元素逐一压入stack，即完成排序。代码如下：

public static void sortStackByStack(Stack<Integer> stack) {
    Stack<Integer> help = new Stack<Integer>();
    while (!stack.isEmpty()) {
        int cur = stack.pop();
        while (!help.isEmpty() && help.peek() < cur) {
            stack.push(help.pop());
        }
        help.push(cur);
    }
    while (!help.isEmpty()) {
        stack.push(help.pop());
    }
}

6，用栈解决汉诺塔问题
题目：经典的汉诺塔问题，现在增加限制，不能从最左侧的塔直接移动到最右侧，也不能从最右侧的塔直接移动到最左侧，而是必须经过中间。
递归的方法代码如下。

public static int hanoiProblem1(int num, String left, String mid,
        String right) {
    if (num < 1) {
        return 0;
    }
    return process(num, left, mid, right, left, right);
}

public static int process(int num, String left, String mid, String right,
        String from, String to) {
    if (num == 1) {
        if (from.equals(mid) || to.equals(mid)) {
            System.out.println("Move 1 from " + from + " to " + to);
            return 1;
        } else {
            System.out.println("Move 1 from " + from + " to " + mid);
            System.out.println("Move 1 from " + mid + " to " + to);
            return 2;
        }
    }
    if (from.equals(mid) || to.equals(mid)) {
        String another = (from.equals(left) || to.equals(left)) ? right : left;
        int part1 = process(num - 1, left, mid, right, from, another);
        int part2 = 1;
        System.out.println("Move " + num + " from " + from + " to " + to);
        int part3 = process(num - 1, left, mid, right, another, to);
        return part1 + part2 + part3;
    } else {
        int part1 = process(num - 1, left, mid, right, from, to);
        int part2 = 1;
        System.out.println("Move " + num + " from " + from + " to " + mid);
        int part3 = process(num - 1, left, mid, right, to, from);
        int part4 = 1;
        System.out.println("Move " + num + " from " + mid + " to " + to);
        int part5 = process(num - 1, left, mid, right, from, to);
        return part1 + part2 + part3 + part4 + part5;
    }
}

非递归的方法代码如下。

public static enum Action {
    No, LToM, MToL, MToR, RToM
}

public static int hanoiProblem2(int num, String left, String mid, String right) {
    Stack<Integer> lS = new Stack<Integer>();
    Stack<Integer> mS = new Stack<Integer>();
    Stack<Integer> rS = new Stack<Integer>();
    lS.push(Integer.MAX_VALUE);
    mS.push(Integer.MAX_VALUE);
    rS.push(Integer.MAX_VALUE);
    for (int i = num; i > 0; i--) {
        lS.push(i);
    }
    Action[] record = { Action.No };
    int step = 0;
    while (rS.size() != num + 1) {
        step += fStackTotStack(record, Action.MToL, Action.LToM, lS, mS, left, mid);
        step += fStackTotStack(record, Action.LToM, Action.MToL, mS, lS, mid, left);
        step += fStackTotStack(record, Action.RToM, Action.MToR, mS, rS, mid, right);
        step += fStackTotStack(record, Action.MToR, Action.RToM, rS, mS, right, mid);
    }
    return step;
}

public static int fStackTotStack(Action[] record, Action preNoAct,
        Action nowAct, Stack<Integer> fStack, Stack<Integer> tStack,
        String from, String to) {
    if (record[0] != preNoAct && fStack.peek() < tStack.peek()) {
        tStack.push(fStack.pop());
        System.out.println("Move " + tStack.peek() + " from " + from + " to " + to);
        record[0] = nowAct;
        return 1;
    }
    return 0;
}

7，生成窗口最大值，有一个整型数组arr和一个大小为w的窗口从数组的最左边滑动到最右边，窗口每次向右滑动一个位置。例如，数组为[4,3,5,4,3,3,6,7]，当窗口大小为3时，
[4,3,5,]4,3,3,6,7 窗口内最大值为5
4,[3,5,4,]3,3,6,7 窗口内最大值为5
4,3,[5,4,3,]3,6,7 窗口内最大值为5
4,3,5,[4,3,3,]6,7 窗口内最大值为4
4,3,5,4,[3,3,6,]7 窗口内最大值为6
4,3,5,4,3,[3,6,7] 窗口内最大值为7
总共产生 n-w+1 个窗口最大值(n:数组长度，w：窗口大小)，实现一个函数：
1，输入：整型数组arr，窗口大小为w。
2，输出：一个长度为n-w+1的数组res，res[i]表示每一种窗口状态下的最大值。
本题的输出结果应该为{5，5，5，4，6，7}。
解题思路：用双端队列来实现窗口最大值的更新，首先生成双端队列，qmax，qmax中存放数组arr中的下标。
假设遍历到arr[i]，qmax的放入规则为：
1，若qmax为空，直接把下标i放进qmax，放入过程结束。
2，若qmax不为空，取出当前qmax队尾存放的下标，假设为i：
1）若arr[j]>arr[i]，直接把下标i存放进qmax的队尾，放入过程结束。
2) 若arr[j]<=arr[i]，把j从qmax中弹出，继续qmax的放入规则。
假设遍历到arr[i]，qmax的弹出规则为：如果qmax队头的下标等于i-w，说明当前qmax队头的下标已过期，弹出当前队头的下标即可。
根据如上的放入和弹出规则，qmax便成了一个维护窗口为w的子数组的最大值更新的结构。下面举例说明题目给出的例子。
1，开始时qmax为空，qmax={}
2，遍历到arr[0]==4，将下标0放入qmax，qmax={0}
3，遍历到arr[1]==3，当前qmax的队尾下标为0，又有arr[0]>arr[1]，所以将下标1放入qmax的尾部，qmax={0,1}
4，遍历到arr[2]==5，当前qmax队尾下标为1，arr[1]

public static int[] getMaxWindow(int[] arr, int w) {
    if (arr == null || w < 1 || arr.length < w) {
        return null;
    }
    LinkedList<Integer> qmax = new LinkedList<Integer>();
    int[] res = new int[arr.length - w + 1];
    int index = 0;
    for (int i = 0; i < arr.length; i++) {
        while (!qmax.isEmpty() && arr[qmax.peekLast()] <= arr[i]) {
            qmax.pollLast();
        }
        qmax.addLast(i);
        if (qmax.peekFirst() == i - w) {
            qmax.pollFirst();
        }
        if (i >= w - 1) {
            res[index++] = arr[qmax.peekFirst()];
        }
    }
    return res;
}

代码如上。
8，构造数组的MaxTree
题目：定义二叉树结构如下：

public static class Node {
        public int value;
        public Node left;
        public Node right;

        public Node(int data) {
            this.value = data;
        }
}

一个数组的MaxTree定义如下：
1),数组必须没有重复元素
2),MaxTree是一颗二叉树，数组的每一个值对应一个二叉树节点
3),包括MaxTree树在内且在其中的每一棵子树上，值最大的节点都是树的头
给定一个没有重复元素的arr，写出生成这个数组的MaxTree的函数，要求如果数组长度为N，则时间复杂度为O(n)，额外空间复杂度为O(n)。
下面举例说明，比如arr={3,4,5,1,2};3的左边第一个比3大的数：无；
3的左边第一个比3大的数：无；3的右边第一个比3大的数：4；
4的左边第一个比4大的数：无；4的右边第一个比4大的数：5；
5的左边第一个比5大的数：无；5的右边第一个比5大的数：无；
1的左边第一个比1大的数：无；1的右边第一个比1大的数：2；
2的左边第一个比1大的数：无；2的右边第一个比2大的数：无；
用以下原则建立这颗树：
1，每一个树的父节点是它左边第一个比他大的数和它右边第一个比它大的树中，较小的那个。
2，如果一个数左边没有比它大的数，右边也没有。也就是说，这个数是整个数组的最大值，那么这个数是MaxTree的头节点。
怎么尽可能找到一个数左右两边第一个比它大的数呢？利用栈。
找每一个数左边的第一个比它大的数，从左到右遍历每个数，栈中保持递减序列，新来的数不停地利用Pop出栈顶，直到栈顶比新数大或没有数。
以[3,1,2]为例，3入栈，接下来1比3小，无须pop3，1入栈，确定了1左边第一个比他大的数为3，接下来2比1大，1出栈，2比3小，2入栈，并且确定了2左边第一个比它大的数是3。用同样的方法可以求出每一个数比它大的数。
以下是getMaxTree代码：

public static Node getMaxTree(int[] arr) {
    Node[] nArr = new Node[arr.length];
    for (int i = 0; i != arr.length; i++) {
        nArr[i] = new Node(arr[i]);
    }
    Stack<Node> stack = new Stack<Node>();
    HashMap<Node, Node> lBigMap = new HashMap<Node, Node>();
    HashMap<Node, Node> rBigMap = new HashMap<Node, Node>();
    for (int i = 0; i != nArr.length; i++) {
        Node curNode = nArr[i];
        while ((!stack.isEmpty()) && stack.peek().value < curNode.value) {
            popStackSetMap(stack, lBigMap);
        }
        stack.push(curNode);
    }
    while (!stack.isEmpty()) {
        popStackSetMap(stack, lBigMap);
    }
    for (int i = nArr.length - 1; i != -1; i--) {
        Node curNode = nArr[i];
        while ((!stack.isEmpty()) && stack.peek().value < curNode.value) {
            popStackSetMap(stack, rBigMap);
        }
        stack.push(curNode);
    }
    while (!stack.isEmpty()) {
        popStackSetMap(stack, rBigMap);
    }
    Node head = null;
    for (int i = 0; i != nArr.length; i++) {
        Node curNode = nArr[i];
        Node left = lBigMap.get(curNode);
        Node right = rBigMap.get(curNode);
        if (left == null && right == null) {
            head = curNode;
        } else if (left == null) {
            if (right.left == null) {
                right.left = curNode;
            } else {
                right.right = curNode;
            }
        } else if (right == null) {
            if (left.left == null) {
                left.left = curNode;
            } else {
                left.right = curNode;
            }
        } else {
            Node parent = left.value < right.value ? left : right;
            if (parent.left == null) {
                parent.left = curNode;
            } else {
                parent.right = curNode;
            }
        }
    }
    return head;
}

public static void popStackSetMap(Stack<Node> stack, HashMap<Node, Node> map) {
    Node popNode = stack.pop();
    if (stack.isEmpty()) {
        map.put(popNode, null);
    } else {
        map.put(popNode, stack.peek());
    }
}

以上是代码。
9，求最大子矩阵的大小
题目：给定一个整型矩阵map，值只有1和0，求全是1的所有矩形区域中，最大的矩形区域为1的数量。
例如：1 1 1 0
其中，最大的矩阵区域有3个1，所以返回3。
思路：1，矩阵行数为n，以每一行为切割，统计以当前行作为底的情况下，每个位置往上的1的数量。使用高度数组height来表示。
例如map =
1 0 1 1
1 1 1 1
1 1 1 0
以第一行切割，height={1,0,1,1}，
以第二行切割，height={2,1,2,2}，
以第三行切割，height={3,2,3,0}，
代码如下：

public static int maxRecSize(int[][] map) {
    if (map == null || map.length == 0 || map[0].length == 0) {
        return 0;
    }
    int maxArea = 0;
    int[] height = new int[map[0].length];
    for (int i = 0; i < map.length; i++) {
        for (int j = 0; j < map[0].length; j++) {
            height[j] = map[i][j] == 0 ? 0 : height[j] + 1;
        }
        maxArea = Math.max(maxRecFromBottom(height), maxArea);
    }
    return maxArea;
}

public static int maxRecFromBottom(int[] height) {
    if (height == null || height.length == 0) {
        return 0;
    }
    int maxArea = 0;
    Stack<Integer> stack = new Stack<Integer>();
    for (int i = 0; i < height.length; i++) {
        while (!stack.isEmpty() && height[i] <= height[stack.peek()]) {
            int j = stack.pop();
            int k = stack.isEmpty() ? -1 : stack.peek();
            int curArea = (i - k - 1) * height[j];
            maxArea = Math.max(maxArea, curArea);
        }
        stack.push(i);
    }
    while (!stack.isEmpty()) {
        int j = stack.pop();
        int k = stack.isEmpty() ? -1 : stack.peek();
        int curArea = (height.length - k - 1) * height[j];
        maxArea = Math.max(maxArea, curArea);
    }
    return maxArea;
}

10，最大值减去最小值小于或等于num的子数组数量
题目：给定数组arr和整数num，共返回有多少个子数组满足如下情况：
max(arr[i..j]) - min(arr[i..j]) <= num
max(arr[i..j])表示子数组arr[i..j]中的最大值，max(arr[i..j])表示子数组arr[i..j]中的最小值。
要求：如果数组长度为n，时间复杂度为O(n)。
思路：首先介绍普通解法，找到arr的所有子数组，一共有n的平方个，然后对每一个子数组做遍历找到其中的最小值和最大值，这个过程时间复杂度为O(n)，然后看子数组是否是满足条件。统计所有满足的子数组数量即可。普通解法时间复杂度是O(nnn)，本书不再详述。而最优解可以做到O(n)，在阅读下面的分析过程之前，先阅读本章的”生成窗口最大值数组”问题，本题所使用到的双端队列结构与解决”生成窗口最大值数组”问题中双端队列结构含义基本一致。
生成两个双端队列qmax和qmin。当子数组为arr[i..j]时，qmax维护了窗口子数组arr[i..j]的最大值更新的结构，qmin维护了窗口子数组arr[i..j]的最小值更新的结构。当子数组arr[i..j]向右扩一个位置变成arr[i..j+1]时，qmax和qmin结构可以在O(1)时间内更新，并且可以在O(1)时间内得到arr[i..j+1]的最大值和最小值。当子数组arr[i..j]向左缩一个位置变成arr[i+1..j]时，qmax和qmin结构依然可以在O(1)时间内更新，并且在O(1)时间内得到arr[i+1..j]的最大值和最小值。
通过分析题目满足的条件，可以得到如下两个结论：
1)，如果子数组arr[i..j]满足条件，即max(arr[i..j]) - min(arr[i..j]) <= num,那么arr[i..j]中的每一个子数组，即arrk..l都满足条件。我们以子数组arr[i..j-1]为例说明，arr[i..j-1]最大值只可能小于或等于arr[i..j]的最大值，arr[i..j]的最小值只可能大于或等于arr[i..j]的最小值，所以arr[i..j-1]必然满足条件。同理，arr[i..j]中的每一个子数组都满足条件。
2),如果子数组不满足条件，那么所有包含arr[i..j]的子数组，即arrk..l都不满足条件。证明过程同第一个结论。
根据双端队列的qmax和qmin的结构性质，以及如上两个结论，设计整个过程如下：
1),生成两个双端队列qmax和qmin，含义如上文所说。生成两个整型变量i和j，表示子数组的范围，即arr[i..j]。生成整型变量res,表示所有满足条件的子数组数量。
2),令j不断向右移动(j++)，表示arr[i..j]一直向右扩大，并不断更新qmax和qmin结构，保证qmax和qmin始终维持动态窗口最大值和最小值的更新结构。一旦出现arr[i..j]不满足条件的情况，j向右扩的过程停止，此时arr[i..j-1]、arr[i..i-2]、arr[i..j-3]、…、arr[i..i]一定都是满足条件的。也就是说，所有必须以arr[i]作为第一个元素的子数组，满足条件的数量为j-1个。于是令res+=j-1。
3),当进行完步骤2时，令i向右移动一个位置，并对qmax和qmin做出相应的更新，qmax和qmin从原来的arr[[i..j]窗口变成arr[i+1..j]窗口的最大值和最小值的更新结构。然后重复步骤2，也就是求所有必须以arr[i+1]作为第一个元素的子数组中，满足条件的数量有多少个。
4),根据步骤2和步骤3，依次求出以arr[0]、arr[1]、…、arr[n-1]作为第一个元素的子数组中满足条件的数量分别有多少个，累加起来的数量就是最终的结果。
上述过程中，所有的下标值最多进qmax和qmin一次，出qmax和qmin一次。i和j的值也不断增加，并且从来不减小。所以整个过程的时间复杂度为O(n)。
最优解请看如下代码的getNum方法： \

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.getFirst()] - arr[qmin.getFirst()] > num) {
                break;
            }
            j++;
        }
        if (qmin.peekFirst() == i) {
            qmin.pollFirst();
        }
        if (qmax.peekFirst() == i) {
            qmax.pollFirst();
        }
        res += j - i;
        i++;
    }
    return res;
}