经典用法
配合滑动窗口，可以快速得到滑动窗口内的最大值或者最小值。如果要最大值，那维护一个大到小队列（存的是下标），如果要最小值，那维护一个小到大的队列。
拿最大值举例：
扩大窗口的时候，判断新加入的元素跟队尾元素的大小，只要队尾元素小于等于新值，则队尾元素出队，直到队尾元素大于新值或者队列为空。然后这个新值的下标从队尾入队
缩小窗口时，判断这个要出去的元素下标跟单调队列队头的下标是否相等，如果相等则队头元素出队。l++.否则就不移除队头。
如果要最大值，就是数组的队头元素位置的值。 nums[deque[l]]
滑动窗口最大值
leetcode 239
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
| public static int[] maxSlidingWindow(int[] arr, int k) {
h = t = 0;
int n = arr.length;
for (int i = 0; i < k - 1; i++) {
while (h < t && arr[deque[t - 1]] <= arr[i]) {
t--;
}
deque[t++] = i;
}
int m = n - k + 1;
int[] ans = new int[m];
for (int l = 0, r = k - 1; l < m; l++, r++) {
while (h < t && arr[deque[t - 1]] <= arr[r]) {
t--;
}
deque[t++] = r;
ans[l] = arr[deque[h]];
if (deque[h] == l) {
h++;
}
}
return ans;
}
|
绝对差不超过限制的最长连续数组
leetcode 1438
思路：利用两个单调队列，一个记录窗口的最小值，一个记录窗口的最大值。窗口开始滑动，每新加一个元素，就维护队列。然后一直缩窗口直到窗口内最大值和最小值之差小于等于limit。之后记录答案，j-i+1。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
| public int longestSubarray(int[] nums, int limit) {
l = 0;
r = 0;
l2 = 0;
r2 = 0;
int n = nums.length;
int ans = 0;
for(int i = 0 , j = 0;j < n; j++){
while( r > l && nums[queue[r-1]] <= nums[j]){
r--;
}
queue[r++] = j;
while( r2 > l2 && nums[queue2[r2-1]] >= nums[j]){
r2--;
}
queue2[r2++] = j;
while( nums[queue[l]] - nums[queue2[l2]] > limit ){
if(queue[l] == i){
l++;
}
if(queue2[l2] == i){
l2++;
}
i++;
}
ans = Math.max(j - i + 1,ans);
}
return ans;
}
|
非经典用法
和至少为K的最短子数组
leetcode 862
思路：计算以每个位置结尾的最小长度。这里最关键的是如果已经算出一个答案的时候，你的窗口右扩，你想找到更短的就只能左缩窗口才行（不用从头开始缩）。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
| public int shortestSubarray(int[] nums, int k) {
l=0;
r=0;
int ans = Integer.MAX_VALUE;
int n = nums.length;
long[] prefix = new long[n + 1];
for (int i = 0; i < n; i++) {
prefix[i + 1] = prefix[i] + nums[i];
}
for(int i =0,j=0;j<=n;j++){
while( l<r && prefix[queue[r-1]] >= prefix[j]){
r--;
}
queue[r++] = j;
if(prefix[j] - prefix[queue[l]] >= k){
while (prefix[j] - prefix[queue[l]] >= k){
if(queue[l] == i){
l++;
}
i++;
}
ans = Math.min(ans,j-i+1);
}
}
return ans == Integer.MAX_VALUE ? -1 : ans;
}
|
满足不等式的最大值
leetcode 1499
给你一个数组 points 和一个整数 k 。数组中每个元素都表示二维平面上的点的坐标，并按照横坐标 x 的值从小到大排序。也就是说 points[i] = [xi, yi] ，并且在 1 <= i < j <= points.length 的前提下， xi < xj 总成立。
请你找出 yi + yj + |xi - xj| 的 最大值，其中 |xi - xj| <= k 且 1 <= i < j <= points.length。
题目测试数据保证至少存在一对能够满足 |xi - xj| <= k 的点。
思路：还是以每个点为结尾。窗口左边从0下标开始，判断是否合法，不合法就左缩窗口，直到合法。这个过程一直记录窗口内点的y-x的最大值。合法之后，用结尾的点加上这个窗口内的最大值就是这个点的对应的最大值，然后把这个点也加入窗口，并且更新单调队列，单调队列以y-x为单调递减。即头部为y-x最大的点。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
| public int findMaxValueOfEquation(int[][] points, int k) {
int n =points.length;
r=0;
l=0;
int ans = Integer.MIN_VALUE;
queue[r++] = 0;
for(int i = 0,j=1;j<n;j++){
while( j>i && points[j][0] - points[i][0] >k){
if(queue[l] == i){
l++;
}
i++;
}
if(i!=j){
int best = queue[l];
ans = Math.max(ans,points[j][0]+points[j][1]-points[best][0]+points[best][1]);
}
while ( l<r && (points[j][1] - points[j][0]) >= (points[queue[r-1]][1]-points[queue[r-1]][0])){
r--;
}
queue[r++] = j;
}
return ans;
}
|
预算内最多机器人的数目
leetcode 2389
思路：单调队列算窗口内的最大值，前缀和算窗口的和。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
| public static final int MAX = 50001;
public static int[] queue =new int[MAX];
public static int l ;
public static int r;
public int maximumRobots(int[] chargeTimes, int[] runningCosts, long budget) {
int n = chargeTimes.length;
r = 0;
l = 0;
int ans = 0;
long[] prefix = new long[n+1];
for(int i =0;i<n;i++){
prefix[i+1] = prefix[i] + runningCosts[i];
}
for(int i=0,j=0;j<n;j++){
while ( l<r && chargeTimes[queue[r-1]] <= chargeTimes[j]){
r--;
}
queue[r++] = j;
while( i<=j && chargeTimes[queue[l]]+ (long) (j - i + 1) *(prefix[j+1]-prefix[i]) > budget){
if(queue[l] == i){
l++;
}
i++;
}
ans = Math.max(ans,j-i+1);
}
return ans;
}
|
wechat