题目及测试
package pid239;
/*滑动窗口最大值给定一个数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。返回滑动窗口中的最大值。示例:输入: nums = [1,3,-1,-3,5,3,6,7], 和 k = 3
输出: [3,3,5,5,6,7]
解释: 滑动窗口的位置 最大值
--------------- -----
[1 3 -1] -3 5 3 6 7 31 [3 -1 -3] 5 3 6 7 31 3 [-1 -3 5] 3 6 7 51 3 -1 [-3 5 3] 6 7 51 3 -1 -3 [5 3 6] 7 61 3 -1 -3 5 [3 6 7] 7提示：你可以假设 k 总是有效的，在输入数组不为空的情况下，1 ≤ k ≤ 输入数组的大小。进阶：你能在线性时间复杂度内解决此题吗？*/
public class main {public static void main(String[] args) {int[][] testTable = {{1,1,2},{1,1,2,2,5,6,7,7},{1,2,3,5},{-1,1,1,1}};int[] testTable2={3,7,4,0};for (int i=0;i<testTable.length;i++) {test(testTable[i],testTable2[i]);}}private static void test(int[] ito,int ito2) {Solution solution = new Solution();int[] rtn;long begin = System.currentTimeMillis();for (int i = 0; i < ito.length; i++) {System.out.print(ito[i]+" ");}//开始时打印数组System.out.println("ito2= "+ito2);rtn = solution.maxSlidingWindow(ito,ito2);//执行程序long end = System.currentTimeMillis(); for (int i = 0; i < rtn.length; i++) {System.out.print(rtn[i]+" ");}//打印结果几数组System.out.println();System.out.println("耗时：" + (end - begin) + "ms");System.out.println("-------------------");}}
没想出来
解法1（别人的）
这是另一个 O(N)的算法。本算法的优点是不需要使用 数组 / 列表 之外的任何数据结构。
算法的思想是将输入数组分割成有 k 个元素的块。
若 n % k != 0，则最后一块的元素个数可能更少。
开头元素为 i ，结尾元素为 j 的当前滑动窗口可能在一个块内，也可能在两个块中。
情况 1 比较简单。 建立数组 left， 其中 left[j] 是从块的开始到下标 j 最大的元素，方向 左->右。
为了处理更复杂的情况 2，我们需要数组 right，其中 right[j] 是从块的结尾到下标 j 最大的元素，方向 右->左。right 数组和 left 除了方向不同以外基本一致。
两数组一起可以提供两个块内元素的全部信息。考虑从下标 i 到下标 j的滑动窗口。 根据定义，right[i] 是左侧块内的最大元素， left[j] 是右侧块内的最大元素。因此滑动窗口中的最大元素为 max(right[i], left[j])。
算法
算法十分直截了当：
从左到右遍历数组，建立数组 left。
从右到左遍历数组，建立数组 right。
建立输出数组 max(right[i], left[i + k - 1])，其中 i 取值范围为 (0, n - k + 1)。
class Solution {public int[] maxSlidingWindow(int[] nums, int k) {int n = nums.length;if (n * k == 0) return new int[0];if (k == 1) return nums;int [] left = new int[n];left[0] = nums[0];int [] right = new int[n];right[n - 1] = nums[n - 1];for (int i = 1; i < n; i++) {// from left to rightif (i % k == 0) left[i] = nums[i]; // block_startelse left[i] = Math.max(left[i - 1], nums[i]);// from right to leftint j = n - i - 1;if ((j + 1) % k == 0) right[j] = nums[j]; // block_endelse right[j] = Math.max(right[j + 1], nums[j]);}int [] output = new int[n - k + 1];for (int i = 0; i < n - k + 1; i++)output[i] = Math.max(left[i + k - 1], right[i]);return output;}
}
解法2（别人的）
可以利用一个双端队列来表示这个窗口。这个双端队列保存当前窗口中最大那个数的下标，双端队列新的头总是当前窗口中最大的那个数。
同时，有了这个下标，我们可以很快地知道新的窗口是否已经不再包含原来那个最大的数，如果不再包含，我们就把旧的数从双端队列的头删除。按照这样的操作，不管窗口的长度是多长，因为数组里的每个数都分别被压入和弹出双端队列一次，所以我们可以在 O(n) 的时间里完成任务。
class Solution {ArrayDeque<Integer> deq = new ArrayDeque<Integer>();int [] nums;public void clean_deque(int i, int k) {// remove indexes of elements not from sliding windowif (!deq.isEmpty() && deq.getFirst() == i - k)deq.removeFirst();// remove from deq indexes of all elements // which are smaller than current element nums[i]while (!deq.isEmpty() && nums[i] > nums[deq.getLast()]) deq.removeLast();}public int[] maxSlidingWindow(int[] nums, int k) {int n = nums.length;if (n * k == 0) return new int[0];if (k == 1) return nums;// init deque and outputthis.nums = nums;int max_idx = 0;for (int i = 0; i < k; i++) {clean_deque(i, k);deq.addLast(i);// compute max in nums[:k]if (nums[i] > nums[max_idx]) max_idx = i;}int [] output = new int[n - k + 1];output[0] = nums[max_idx];// build outputfor (int i = k; i < n; i++) {clean_deque(i, k);deq.addLast(i);output[i - k + 1] = nums[deq.getFirst()];}return output;}
}