题解 | #滑动窗口的最大值# [P0-T2]

在第i个数要找左侧窗口内的最大数。所以又可以单调栈套娃
唯一需要变化的就是栈上只保留窗口以内的数，所以栈上存下标以查看栈上最老的数是否还在窗口内。

再来一遍口诀：
找右边的就从右往左，找左边的从左往右
找小的就递增，找大的就递减

这里找左边最大, 那就是从左向右+递减。

import java.util.*;

// 找左边最大 -> 从左向右 (非单调)递减
public class Solution {
    public ArrayList<Integer> maxInWindows(int[] num, int size) {
      ArrayList<Integer> ans = new ArrayList<>();
      if (size > num.length || size == 0) return ans;
      
      Deque<Integer> dq = new ArrayDeque<>();
      for (int i = 0; i < num.length; i++) {
        if (!dq.isEmpty() && dq.peekFirst() <= i-size)
          dq.pollFirst();  // remove oldest number if outside window
        
        // 以满足非单调递减
        while(!dq.isEmpty() && num[i] >= num[dq.peekLast()])
          dq.pollLast();
        dq.offerLast(i);
        
        if (i >= size - 1)
          ans.add(num[dq.peekFirst()]); // dq从前向后递减 -> first最大
      }
      
      return ans;
    }
}