单调队列

239. 滑动窗口最大值

给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
返回滑动窗口中的最大值。

• 对于新的index，先判断当前的对头元素所指向位置是不是已经超出了本窗口，超出则删除队头
• 如果新来的元素[index]比队尾大，while删除队尾（因为新加入的元素一定可以覆盖掉当前队尾可以覆盖的区间）
• 加入当前index作为队尾
• 将队头元素作为当前窗口的最大值出栈

  class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        Deque<Integer> deque = new LinkedList<Integer>();
        int[] res = new int[nums.length-k+1];
        int l = 0;
        for(int i = 0 ; i < nums.length;i++) {
            if(deque.size()>0 && i -k + 1 > deque.peekFirst()) deque.removeFirst();
            while(deque.size()>0 && nums[deque.peekLast()] <= nums[i]) deque.pollLast();
            deque.offerLast(i);
            if(i-k+1>=0) res[l++] = nums[deque.peekFirst()];
        }
        return res;
    }
  }

918. 环形子数组的最大和

给定一个由整数数组 A 表示的环形数组 C，求 **C** 的非空子数组的最大可能和。
在此处，环形数组意味着数组的末端将会与开头相连呈环状。（形式上，当0 <= i < A.length 时 C[i] = A[i]，且当 i >= 0 时 C[i+A.length] = C[i]）
此外，子数组最多只能包含固定缓冲区 A 中的每个元素一次。（形式上，对于子数组 C[i], C[i+1], ..., C[j]，不存在 i <= k1, k2 <= j 其中 k1 % A.length = k2 % A.length）

• 使用一个两倍长度的前缀和数组

• 对于i位置的前缀和，减去前面单倍长度的区间中前缀和的最小值

  class Solution {
    public int maxSubarraySumCircular(int[] A) {
        int max = -30000 -1;
        int[] s = new int[A.length*2];
        s[0] = A[0];
        for(int i =0 ; i < A.length;i++) {
            max = Math.max(max,A[i]);
            s[i] = s[i+A.length]= A[i];
        }
        for(int i = 1 ; i < s.length;i++) {
            s[i] = s[i-1] + s[i];
        }
        Deque<Integer> q = new LinkedList<>();
        int len = A.length-1;
        for(int i = 0 ; i < s.length ; i++) {
            if(q.size()>0) {
                max = Math.max(s[i]-s[q.getFirst()],max);
            }
            if(q.size()>0 && i-len>q.getFirst()) q.pollFirst();
            while(q.size() >0 && s[q.getLast()]>=s[i]) q.pollLast();
            q.addLast(i);
        }
        return max;
    }
  }