经典用法
配合滑动窗口，可以快速得到滑动窗口内的最大值或者最小值。如果要最大值，那维护一个大到小队列（存的是下标），如果要最小值，那维护一个小到大的队列。
拿最大值举例：
扩大窗口的时候，判断新加入的元素跟队尾元素的大小，只要队尾元素小于等于新值，则队尾元素出队，直到队尾元素大于新值或者队列为空。然后这个新值的下标从队尾入队
缩小窗口时，判断这个要出去的元素下标跟单调队列队头的下标是否相等，如果相等则队头元素出队。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;
}
|
三个无重叠子数组的最大和
leetcode 689
思路：化成三个部分，中间部分一定为i…i+k-1,左边为0….i-1 右边为i+k…n-1。此时只要知道截至到i位置最大的开始下标就可以知道前面的最大值。知道从i位置到n-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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
| public int[] maxSumOfThreeSubarrays(int[] nums, int k) {
int n = nums.length;
int sumNum = 0;
int[] sum = new int[n-k+1];
for(int l=0,r=0;r<n;r++){
sumNum+=nums[r];
if(r-l+1 == k){
sum[l] = sumNum;
sumNum-=nums[l];
l++;
}
}
int[] queue = new int[n];
int l=0,r=0;
int[] prefix = new int[n];
queue[r++] = 0;
for(int i=k;i<n;i++){
while(l<r && sum[queue[l]] < sum[i-k+1]){
r--;
}
queue[r++] = i-k+1;
prefix[i] = queue[l];
}
l=0;
r=0;
int[] suffix = new int[n];
suffix[n-k] = n-k;
queue[r++] = n-k;
for(int i = n-k-1;i>=0;i--){
while(l<r && sum[queue[l]] <= sum[i]){
r--;
}
queue[r++] = i;
suffix[i] = queue[l];
}
int a=0,b=0,c=0,max=0;
for(int i= k,j=k*2-1;j<n-k;i++,j++){
int m = prefix[i-1];
int p = suffix[j+1];
int all = sum[m] + sum[i] + sum[p];
if(all > max){
max = all;
a=m;
b=i;
c=p;
}
}
return new int[]{a,b,c};
}
|
wechat