算法学习-单调双端队列

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        int n=nums.length;
        int[]ans=new int[n-k+1];
        Deque<Integer> que=new ArrayDeque<>();
        for(int i=0;i<n;i++){
            //控制队尾元素出队
            while(!que.isEmpty()&&nums[i]>nums[que.peekLast()]) que.pollLast();
          	//出队以后就进队
            que.offerLast(i);
            
            //判断是否当前的值都在窗口范围k内，如果过大需要队头出队
			//当前i加入以后判断，合理窗口范围[i-k+1,i]，因此pollFirst()下界-1
            while(!que.isEmpty()&&i-k>=que.peekFirst()) que.pollFirst();
            
            //当前窗口长度>=k时，保存答案
            if(i+1>=k){
                //每次答案就是队头元素
                ans[i-k+1]=nums[que.peekFirst()];
            }
        }
        return ans;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

也可以将判断窗口过大的限制放在队尾出队以前，因为当前即将队尾入队的元素本身就不会被出队干扰，一定会进入的，出队只是排除队列头部的窗口外元素。队尾入队一定要在队尾出队以后，比如[1,2,3],k=1，窗口限制在前，1加入，然后下一循环，1算出来在窗口外，被排出，然后尾部直接进入；如果尾部出队在前，1加入，窗口限制0-1=-1<0，然后下一循环，2将前面尾部挤出，队中只有2不需要被窗口限制。

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        int n=nums.length;
        int[]ans=new int[n-k+1];
        Deque<Integer> que=new ArrayDeque<>();
        for(int i=0;i<n;i++){
            //判断是否窗口过大，需要队头出队
            while(!que.isEmpty()&&i-k>=que.peekFirst()) que.pollFirst();
            
            //控制队尾元素出队
            while(!que.isEmpty()&&nums[i]>nums[que.peekLast()]) que.pollLast();
            //元素进队
            que.offerLast(i);
            
            //当前窗口长度>=k时，保存答案
            if(i+1>=k){
                //每次答案就是队头元素
                ans[i-k+1]=nums[que.peekFirst()];
            }
        }
        return ans;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

上面的写法循环从0开始，整个过程涵盖了将窗口填满成k，然后继续往里面加。还有一种写法是先将窗口填满k，最后记录答案的第一个数字，然后循环从k开始继续往里面加入后面的数字，同时记录答案。本质上没区别，上面写法在窗口不到k的时候，也不用判断范围也不需要保存答案，但是控制队尾元素出队两种做法都是要一直进行的。

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        int n=nums.length;
        ArrayDeque<Integer> que=new ArrayDeque<>();
        int[]ans=new int[n-k+1];
        int i=0;
        for(;i<k;i++){
            while(!que.isEmpty()&&nums[i]>nums[que.peekLast()]){
                que.pollLast();
            }
            que.offerLast(i);
        }
        ans[0]=nums[que.peekFirst()];
        
        for(;i<n;i++){
            //入队时判断队尾元素出队
            while(!que.isEmpty()&&nums[i]>nums[que.peekLast()]){
                que.pollLast();
            }
            //维护当前目标窗口的范围
            while(!que.isEmpty()&&i-k>=que.peekFirst()){
                que.pollFirst();
            }
            que.offerLast(i);
            ans[i-k+1]=nums[que.peekFirst()];
        }

        return ans;
    }
}
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

1438.绝对差不超过限制的最长连续子数组

单调双端队列+滑动窗口。为了计算当前窗口的最大绝对值之差，需要单调队列，维护当前的最大值和最小值，队列中存的是元素值。队列限制条件为满足limit条件，但为了求窗口的最大值，额外维护一个left左边界，相当于是维护了一个滑动窗口，也满足right右移绝对值可能值变多，left左移绝对值可能值变少的单调性。

这题也可以将主框架看作是滑动窗口，不同于之前我滑动窗口专题仅需维护一个满足限制条件的滑动窗口，引路->算法学习-滑动窗口，这里在维护滑动窗口时，相当于窗口中是用单调队列维护的最值。

class Solution {
    public int longestSubarray(int[] nums, int limit) {
        int right=0;
        int left=0;
        int res=0;
        int len=nums.length;
        Deque<Integer> minq=new ArrayDeque<>();
        Deque<Integer> maxq=new ArrayDeque<>();
        for(;right<len;right++){
            //单调队列队尾入队的出队操作
            while(!minq.isEmpty()&&nums[right]<minq.peekLast()){
                minq.pollLast();
            }
            minq.offerLast(nums[right]);
            while(!maxq.isEmpty()&&nums[right]>maxq.peekLast()){
                maxq.pollLast();
            }
            maxq.offerLast(nums[right]);

            //维护当前差值的窗口范围
            while(maxq.peekFirst()-minq.peekFirst()>limit){
                //单调队列的限制操作，更新最值
                //当前滑动窗口最左侧left的值和单调队列最左侧一样的话，单调队列一定得更新
                if(!maxq.isEmpty()&&maxq.peekFirst()==nums[left]) maxq.pollFirst();
                if(!minq.isEmpty()&&minq.peekFirst()==nums[left]) minq.pollFirst();
                //绝对值之差不满足的话，left无论如何一定要++
                left++;
            }
            //外部捕获结果
            res=Math.max(res,right-left+1);
        }
        return res;
    }
}
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

862.和至少为K的最短子数组

前缀和+单调递增队列+滑动窗口，队列中存的是前缀和下标，因为这样子就可以通过下标索引前缀和数组求区间和，作差求出长度，单调递增队列贪心地在队首维护当前最小前缀和下标，当前前缀和preSum[right]减去preSum[minq.peekFirst()]是尽可能大的，可以尽快找到和至少为K的子数组，对满足和为K的答案用res不断取最小值就可以。其中在维护队尾时，如果新加入进来的前缀和比minq.peekLast()小，队尾出队，因为入队元素后面的subarray前缀和以及作差算出来的长度肯定都优于前面出队的元素。限制条件中，滑动窗口计算当前前缀和与preSum[minq.peekFirst()]的差，如果>=K，代表minq.peekFirst()已经找到了满足条件的最近解，将其出队，合法缩小左边界。

其中缩小左边界不同于上题1438.绝对差不超过限制的最长连续子数组，没有维护一个left左边界变量，其原因是这里要是找最短子数组，每次减去minq.peekFirst()可以尽快缩小子数组长度，和上面需要找最长子数组不同慢慢减不同。

class Solution {
    public int shortestSubarray(int[] nums, int k) {
        int len=nums.length;
        long []preSum=new long[len+1];
        for(int i=0;i<len;i++){
            preSum[i+1]=preSum[i]+nums[i];
        }

        //维护单调递增队列
        ArrayDeque<Integer> minq=new ArrayDeque<>();
        int right=0;
        int res=Integer.MAX_VALUE;
        for(;right<=len;right++){
            //取等于号，将最小值往后靠，尽可能缩小后面满足条件的长度
            while(!minq.isEmpty()&&preSum[right]<=preSum[minq.peekLast()]){
                minq.pollLast();
            }
            minq.offerLast(right);

            //合法缩小滑动窗口范围
            while(!minq.isEmpty()&&preSum[right]-preSum[minq.peekFirst()]>=k){
                //由于是前缀的形式，所以minq.peekFirst()不包含区间的第一个元素，直接相减就是区间长度
                res=Math.min(res,right-minq.peekFirst());
                minq.pollFirst();
            }
        }
        return res==Integer.MAX_VALUE?-1:res;
    }
}
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

class Solution:
    def shortestSubarray(self, nums: List[int], k: int) -> int:
        presum=[0]*(len(nums)+1)
        res=inf
        for i,c in enumerate(nums):
            presum[i+1]=presum[i]+c
        q=collections.deque()
        for i,c in enumerate(presum):
            while q and c <= presum[q[-1]]:
                q.pop()
            q.append(i)
            while q and presum[q[-1]]-presum[q[0]]>=k:
                res=min(res,q[-1]-q[0])
                q.popleft()
        return res if res !=inf else -1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

1425.带限制的子序列和

子序列DP+单调队列+滑动窗口。间断子序列和最大值的问题，很容易想到子序列dp，设dp[i]是以nums[i]结尾的子序列的最大和，且当i>=k时，dp[i]=Math.max(nums[i],nums[i]+dp[i-1],nums[i]+dp[i-2]....,nums[i]+dp[i-k])，从左到右遍历所有nums元素，时间复杂度为O(NK)，会超时。优化就是，也在遍历的过程中，时刻维护当前元素前的最大dp[i]，限制条件就下标最多到前面的dp[i-k]，队列中存的是dp[i]的下标，这个区间的维护就很像239.滑动窗口最大值的滑动窗口，但其中维护目标窗口大小略有区别，239是要产生当前窗口的答案，因此维护的是当前窗口的k个数，然后记录答案，而1425在刚开始就已经可以用res记录答案，它是为下一个dp的窗口维护k个数的最大值。

子序列和单调队列从左到右遍历一遍，就可以维护子序列的最大值以及单调队列的最大值，时间复杂度为O(N)。

class Solution {
    public int constrainedSubsetSum(int[] nums, int k) {
        int len=nums.length;
        int[]dp=new int[len];
        dp[0]=nums[0];
        int res=dp[0];
        Deque<Integer> maxq=new ArrayDeque<>();
        maxq.offerLast(0);
        int right=1;
        for(;right<len;right++){
            //这里必须得先计算下一个待入队的元素，不然没法维护单调性
            //k至少为1，dp[right]的这一步计算肯定合法
            dp[right]=Math.max(dp[maxq.peekFirst()]+nums[right],nums[right]);
            //维护一个单调递减队列
            while(!maxq.isEmpty()&&dp[right]>dp[maxq.peekLast()]){
                maxq.pollLast();
            }
            maxq.offerLast(right);

            //维护下一个数的前k个数目标范围
            //当前窗口范围[right-k+1,right],因此pollFirst()下界-1
            while(!maxq.isEmpty()&&right-k>=maxq.peekFirst()) maxq.pollFirst();

            res=Math.max(res,dp[right]);
        }
        return res;
    }
}
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

1499.满足不等式的最大值

单调递减队列+滑动窗口。因为 xi，对于遍历的每个(xi,xj)来说，需要加上前面yi-xi的最大值，才有可能使得整体最大，因此采用单调递减队列从队列头取最大值。滑动窗口的限制条件为xj-xi<=k，这也正是由于xi单调递增，因此可以从右到左进行限制。为了能够在队列中同时计算上面的值，队列中存储元素下标。

class Solution {
    public int findMaxValueOfEquation(int[][] points, int k) {
       int len=points.length;
       ArrayDeque<Integer> maxq=new ArrayDeque<>();
       int right=0;
       int res=Integer.MIN_VALUE;
       for(;right<len;right++){
           //维护当前的窗口大小
           while(!maxq.isEmpty()&&points[right][0]-points[maxq.peekFirst()][0]>k) maxq.pollFirst();
           if(!maxq.isEmpty()) res=Math.max(res,points[maxq.peekFirst()][1]-points[maxq.peekFirst()][0]+points[right][1]+points[right][0]);

           int gap=points[right][1]-points[right][0];
           while(!maxq.isEmpty()&&gap>points[maxq.peekLast()][1]-points[maxq.peekLast()][0]){
               maxq.pollLast();
           }
           maxq.offerLast(right);
       }
       return res;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

class Solution {
    public int maximumRobots(int[] chargeTimes, int[] runningCosts, long budget) {
        long sum=0;
        Deque<Integer> maxq=new ArrayDeque<>();
        int len=chargeTimes.length;
        int res=0;
        for(int left=0,right=0;right<len;right++){
            //维护到当前为止的和
            sum+=runningCosts[right];
            //维护到当前为止的最大值
            while(!maxq.isEmpty()&&chargeTimes[right]>chargeTimes[maxq.peekLast()]){
                maxq.pollLast();
            }
            maxq.offerLast(right);

            //维护当前窗口的范围
            while(!maxq.isEmpty()&&chargeTimes[maxq.peekFirst()]+1L*(right-left+1)*sum>budget){
                //左边界缩小时检查队列中的数字是否需要跟着改变
                if(maxq.peekFirst()==left) maxq.pollFirst();
                sum-=runningCosts[left++];
            }
            res=Math.max(res,right-left+1);
        }
        return res;
    }
}
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