一、239.Sliding Window Maximum
Given an array nums, there is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves right by one position. Return the max sliding window.
Example:
代码语言：javascript复制Input: nums = [1,3,-1,-3,5,3,6,7], and k = 3
Output: [3,3,5,5,6,7]
Explanation:
Window position Max
--------------- -----
[1 3 -1] -3 5 3 6 7 3
1 [3 -1 -3] 5 3 6 7 3
1 3 [-1 -3 5] 3 6 7 5
1 3 -1 [-3 5 3] 6 7 5
1 3 -1 -3 [5 3 6] 7 6
1 3 -1 -3 5 [3 6 7] 7时间复杂度是O(N)
代码语言：javascript复制
public int[] maxSlidingWindow(int[] nums, int k) {
if (nums == null ||k < 1||nums.length<k) return new int[nums.length];
int [] res = new int[nums.length - k 1];
LinkedList<Integer> DQueue = new LinkedList<>();
int index = 0;
for (int i = 0 ; i < nums.length;i ){
//当前的树与队列尾部的数相比较，如果尾部的数比当前的数小，则弹出
while (!DQueue.isEmpty() && nums[DQueue.getLast()] <= nums[i]){
DQueue.pollLast();
}
DQueue.addLast(i);
//加入了新的数，那么就要将头部的数删除
if (DQueue.getFirst() == i - k){
DQueue.pollFirst();
}
if (i >= k - 1){
res[index ] = nums[DQueue.peekFirst()];
}
}
return res;
} 二、求子数组中的最大值与最小值之差小于num的个数
O(N)的解法，用一个双端队列记录窗口中最大值，一个记录最小值。
代码语言：javascript复制public static int allLessNumSubArr(int [] arr,int num){
if (arr == null || arr.length == 0) return 0;
int res = 0;
LinkedList <Integer> max = new LinkedList<>();
LinkedList <Integer> min = new LinkedList<>();
int right = 0;
for (int left = 0 ;left < arr.length; left ){
while(right < arr.length){
while (!max.isEmpty() && arr[max.peekLast()] <= arr[right]){
max.pollLast();
}
max.addLast(right);
while (!min.isEmpty() && arr[min.peekLast()] >= arr[right]){
min.pollLast();
}
min.addLast(right);
if (arr[max.peekFirst()] - arr[min.peekFirst()] > num)
break;
right ;
}
if (min.peekFirst() == left){
min.pollFirst();
}
if (max.peekFirst() == left){
max.pollFirst();
}
res = right - left;
left ;
}
return res;
}
