Sliding Window Maximum：如何将每次滑动窗口内的最值保存

Given an arraynums, there is a sliding window of sizekwhich is moving from the very left of the array to the very right. You can only see theknumbers in the window. Each time the sliding window moves right by one position.

For example,
Givennums=[1,3,-1,-3,5,3,6,7], andk= 3.

Window position                Max
---------------               -----
[1  3  -1] -3  5  3  6  7       3
 1 [3  -1  -3] 5  3  6  7       3
 1  3 [-1  -3  5] 3  6  7       5
 1  3  -1 [-3  5  3] 6  7       5
 1  3  -1  -3 [5  3  6] 7       6
 1  3  -1  -3  5 [3  6  7]      7

Therefore, return the max sliding window as[3,3,5,5,6,7].

Note:
You may assumekis always valid, ie: 1 ≤ k ≤ input array's size for non-empty array.

思路：参见https://leetcode.com/problems/sliding-window-maximum/discuss/，其中以个非常有趣的思路是这样：

例如: A = [2,1,3,4,6,3,8,9,10,12,56], w=4

将数组以大小为w = 4分块，最后一块可能小于 w.
2, 1, 3, 4 | 6, 3, 8, 9 | 10, 12, 56|

从左向右遍历找出当前最值. 当遇到每块的边界时重置最值 (相当于每w个元素).
left_max[] = 2, 2, 3, 4 | 6, 6, 8, 9 | 10, 12, 56

从右向左遍历找出当前最值. 当遇到每块的边界时重置最值.
right_max[] = 4, 4, 4, 4 | 9, 9, 9, 9 | 56, 56, 56

当前窗口左边界对应位置i，寻找当前位置i对应最值：sliding-max(i) = max{right_max(i), left_max(i+w-1)}
sliding_max = 4, 6, 6, 8, 9, 10, 12, 56

这里每段窗口内都恰好被两个区域所覆盖，所每个区域的最值都已实现求出（两次扫描的结果）。对于w的选择，只要分割的大小不会使大小为w的窗内出现第三块区域、或者没有不能被已得到最值区域覆盖的情况即可，有预测样例里包括w=1.所以设置分割大小为w-1无法过样例。

class Solution {
    public int[] maxSlidingWindow(int[] in, int w) {
        if(in.length==0) return new int[0]; 
        
        final int[] max_left = new int[in.length];
        final int[] max_right = new int[in.length];

        max_left[0] = in[0];
        max_right[in.length - 1] = in[in.length - 1];

        for (int i = 1; i < in.length; i++) {
            max_left[i] = (i % w == 0) ? in[i] : Math.max(max_left[i - 1], in[i]);

            final int j = in.length - i - 1;
            max_right[j] = (j % w == 0) ? in[j] : Math.max(max_right[j + 1], in[j]);
        }

        final int[] sliding_max = new int[in.length - w + 1];
        for (int i = 0, j = 0; i + w <= in.length; i++) {
            sliding_max[j++] = Math.max(max_right[i], max_left[i + w - 1]);
        }

        return sliding_max;
        }
}

这个思路和之前做过的矩形面积非常相似，只不过队列内保存的是元素递减序列，且保存的为下标值。当前元素若大于队尾元素，则将队尾中保存的下标删除，直到不满足条件或者队列为空，然后将其下标添加至队尾。滑动窗口时，队首中保存的下标的删除取决于队首保存的下标对应的元素是否滑出窗口。

下面的代码是将窗口的右边界当做窗口首部，从左向右移动，最开始前k-1个位置窗口没有被填充满，这样的好处是不用先向队列添加元素，所以填充答案时，判断条件是窗口是否被填充满。

public int[] maxSlidingWindow(int[] a, int k) {		
		if (a == null || k <= 0) {
			return new int[0];
		}
		int n = a.length;
		int[] r = new int[n-k+1];
		int ri = 0;
		// store index
		Deque q = new ArrayDeque<>();
		for (int i = 0; i < a.length; i++) {
			// remove numbers out of range k
			while (!q.isEmpty() && q.peek() < i - k + 1) {
				q.poll();
			}
			// remove smaller numbers in k range as they are useless
			while (!q.isEmpty() && a[q.peekLast()] < a[i]) {
				q.pollLast();
			}
			// q contains index... r contains content
			q.offer(i);
			if (i >= k - 1) {
				r[ri++] = a[q.peek()];
			}
		}
		return r;
	}