一、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:
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)
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)的解法,用一個雙端隊列記錄視窗中最大值,一個記錄最小值。
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;
}
複制