题目

给定数组arr和整数num，求数组的子数组中有多少个的满足“最大值减去最小值<=num”。

解题思路

• 分析题目，有结论：
  • 如果数组arr[i...j]满足条件，则它的每一个子数组都满足条件。
  • 如果数组arr[i...j]不满足条件，则包含它的每一个数组都不满足条件。
• 数据结构：用i、j表示当前窗口，分别使用两个双端队列维护窗口的最大值和最小值。
• 具体地，每次更新两个双端队列，检查当前的窗口是否满足条件，满足则j++，不满足则cnt+=j-i,更新双端队列，i++，j不变。若j到了len，则当前趟和剩余未遍历的都满足条件，加到cnt中。
• 时间复杂度：i，j只需遍历一趟，时间复杂度O(n)。

代码

import java.util.LinkedList;

public class Main {

	public static void main(String args[]) {

		int[] arr = { 1, 3, 2, 4, 5 };

		int num = 1;

		int cnt = subArrayNum(arr, num);

		System.out.println(cnt);

	}

	public static int subArrayNum(int[] arr, int num) {

		int cnt = 0;

		LinkedList<Integer> maxQue = new LinkedList<>();

		LinkedList<Integer> minQue = new LinkedList<>();

		int i = 0;

		int j = 0;

		while (i < arr.length) {

			while (j < arr.length) {

				while (!maxQue.isEmpty() && arr[maxQue.peekLast()] <= arr[j]) {

					maxQue.pollLast();

				}

				maxQue.addLast(j);

				while (!minQue.isEmpty() && arr[minQue.peekLast()] >= arr[j]) {

					minQue.pollLast();

				}

				minQue.add(j);

				if (arr[maxQue.peekFirst()] - arr[minQue.peekFirst()] > num) {

					cnt += j - i;

					if (maxQue.peekFirst() == i) {

						maxQue.pollFirst();

					}

					if (minQue.peekFirst() == i) {

						minQue.pollFirst();

					}

					break;// 如果break ,j不++，因为当前arr[i...j]不满足条件，不能保证arr[i+1...j]满足条件

				}

				++j;

				if (j == arr.length) {// 说明此趟以及后面未遍历的趟的子数组全部满足条件。

					for (; i < arr.length; ++i) {

						cnt += j - i;

					}

					break;

				}

			}

			++i;

		}

		return cnt;

	}

}