滑动窗口最大值-leetcode

题目描述

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

返回 滑动窗口中的最大值 。

示例 1：

输入：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

示例 2：

输入：nums = [1], k = 1
输出：[1]

提示：

• 1 <= nums.length <= 105
• -104 <= nums[i] <= 104
• 1 <= k <= nums.length

解法一

思路：

记录当前窗口中的最大值，当窗口右移时，新的元素进入窗口，同时也要删除元素，左侧删除的元素可能就是最大值的位置，那么就要重新选择最大值，若删除的元素不是最大值，则直接删除，在比较新的元素的大小。

代码：

class Solution {public int[] maxSlidingWindow(int[] nums, int k) {//记录最大值windowMaxint windowMax = Integer.MIN_VALUE;//记录窗口位置int left=0;int[] res = new int[nums.length-k+1];int count=0;//对于第一个窗口进行处理for(int i=0;i<k;i++){if(windowMax<nums[i])windowMax=nums[i];}res[count++] = windowMax;for(int i=k; i<nums.length; i++) {//如果移除的数据是最大值，就需要重新确定最大值if(nums[left]==windowMax&&nums[left+1]!=windowMax){windowMax=Integer.MIN_VALUE;for(int j=left+1;j<i+1;j++){if(windowMax<nums[j])windowMax=nums[j];}}if(windowMax<nums[i]) windowMax=nums[i];res[count++] = windowMax;left++;}return res;}
}public class leetcode_010 {public static int subarraySum(int[] nums, int k) {int ans=0;int tempSum=0;for(int i=0;i<nums.length;i++){tempSum+=nums[i];if(tempSum==k)ans++;for (int j=i+1;j<nums.length;j++){tempSum+=nums[j];if(tempSum==k)ans++;}tempSum=0;}return ans;}public static void main(String[] args) {Scanner sc = new Scanner(System.in);String[] line = sc.nextLine().split(",");int[] nums= Arrays.stream(line).mapToInt(Integer::parseInt).toArray();int k = sc.nextInt();int res = subarraySum(nums,k);System.out.println(res);}
}

注意：

若是采用stream流的方式来寻找最大值，那么这样比单层循环更加的耗时。

解法二

思路：

来自官方的解答，采用优先队列。

java的优先队列就是堆结构（大根堆），窗口右移，一个元素进入优先队列中，此时，判断当前的队首元素是否还在窗口中，若还在，那么就是当前最大值，否则就要移除队首元素，直至新的队首元素在窗口中。

代码：

class Solution {public int[] maxSlidingWindow(int[] nums, int k) {int n = nums.length;//队列中存储的是数组，第一个元素是值，第二个元素是索引PriorityQueue<int[]> pq = new PriorityQueue<int[]>(new Comparator<int[]>() {public int compare(int[] pair1, int[] pair2) {//若值不想等，则按值降序排列，否则按索引降序排列return pair1[0] != pair2[0] ? pair2[0] - pair1[0] : pair2[1] - pair1[1];}});for (int i = 0; i < k; ++i) {pq.offer(new int[]{nums[i], i});}int[] ans = new int[n - k + 1];ans[0] = pq.peek()[0];for (int i = k; i < n; ++i) {pq.offer(new int[]{nums[i], i});while (pq.peek()[1] <= i - k) {pq.poll();}ans[i - k + 1] = pq.peek()[0];}return ans;}
}

解法三

思路：

来自官方的解答，采用双端队列。

由于我们需要求出的是滑动窗口的最大值，如果当前的滑动窗口中有两个下标 i 和 j，其中 i 在 j 的左侧（i<j），并且 i 对应的元素不大于 j 对应的元素（nums[i]≤nums[j]），那么会发生什么呢？

当滑动窗口向右移动时，只要 i 还在窗口中，那么 j 一定也还在窗口中，这是 i 在 j 的左侧所保证的。因此，由于 nums[j] 的存在，nums[i] 一定不会是滑动窗口中的最大值了，我们可以将 nums[i] 永久地移除。

因此我们可以使用一个队列存储所有还没有被移除的下标。在队列中，这些下标按照从小到大的顺序被存储，并且它们在数组 nums 中对应的值是严格单调递减的。

当滑动窗口向右移动时，我们需要把一个新的元素放入队列中。为了保持队列的性质，我们会不断地将新的元素与队尾的元素相比较，如果新加入的元素比队尾元素大，那么队尾元素永远不会成为最大值，因为，新加入的元素一定在窗口中，可以直接删除队尾元素，再与新的队尾元素进行比较，若是新加入的元素比队尾元素小，那么直接加入队尾。此时在判断队首元素是否在窗口中，不在就移除。

代码：

class Solution {public int[] maxSlidingWindow(int[] nums, int k) {int n = nums.length;//双端队列，采用LinkedList实现Deque<Integer> deque = new LinkedList<Integer>();for (int i = 0; i < k; ++i) {while (!deque.isEmpty() && nums[i] >= nums[deque.peekLast()]) {deque.pollLast();}deque.offerLast(i);}int[] ans = new int[n - k + 1];ans[0] = nums[deque.peekFirst()];for (int i = k; i < n; ++i) {while (!deque.isEmpty() && nums[i] >= nums[deque.peekLast()]) {deque.pollLast();}deque.offerLast(i);while (deque.peekFirst() <= i - k) {deque.pollFirst();}ans[i - k + 1] = nums[deque.peekFirst()];}return ans;}
}

解法四

思路：

来自官方的解答，采用分块的思想。

我们可以将数组nums从左到右按照 k 个一组进行分组，最后一组中元素的数量可能会不足 k 个。如果我们希望求出 nums[i] 到 nums[i+k−1] 的最大值，就会有两种情况：

• 如果 i 是k的倍数，那么nums[i]到 nums[i+k−1] 恰好是一个分组。我们只要预处理出每个分组中的最大值，即可得到答案；

• 如果 i 不是k的倍数，那么 nums[i] 到nums[i+k−1]会跨越两个分组，占有第一个分组的后缀以及第二个分组的前缀。假设 j 是 k 的倍数，并且满足 i<j≤i+k−1，即j是两个分组的边界且j属于第二个分组的起始，那么 nums[i] 到 nums[j−1] 就是第一个分组的后缀，nums[j] 到 nums[i+k−1] 就是第二个分组的前缀。如果我们能够预处理出每个分组中的前缀最大值以及后缀最大值，同样可以在 O(1) 的时间得到答案。

因此我们用 prefixMax[i] 表示下标i对应的分组中，以 i 结尾的前缀最大值；suffixMax[i] 表示下标i对应的分组中，以 i 开始的后缀最大值。它们分别满足如下的递推式

以及

需要注意在递推 suffixMax[i] 时需要考虑到边界条件 suffixMax[n−1]=nums[n−1]，而在递推 prefixMax[i] 时的边界条件 prefixMax[0]=nums[0] 恰好包含在递推式的第一种情况中，因此无需特殊考虑。

在预处理完成之后，对于 nums[i] 到 nums[i+k−1] 的所有元素，如果i不是 k 的倍数，那么窗口中的最大值为 suffixMax[i] 与 prefixMax[i+k−1]中的较大值；如果i是k的倍数，那么此时窗口恰好对应一整个分组，suffixMax[i] 和 prefixMax[i+k−1] 都等于分组中的最大值，因此无论窗口属于哪一种情况，

即为答案。

代码：

class Solution {public int[] maxSlidingWindow(int[] nums, int k) {int n = nums.length;int[] prefixMax = new int[n];int[] suffixMax = new int[n];for (int i = 0; i < n; ++i) {if (i % k == 0) {prefixMax[i] = nums[i];}else {prefixMax[i] = Math.max(prefixMax[i - 1], nums[i]);}}for (int i = n - 1; i >= 0; --i) {if (i == n - 1 || (i + 1) % k == 0) {suffixMax[i] = nums[i];} else {suffixMax[i] = Math.max(suffixMax[i + 1], nums[i]);}}int[] ans = new int[n - k + 1];for (int i = 0; i <= n - k; ++i) {ans[i] = Math.max(suffixMax[i], prefixMax[i + k - 1]);}return ans;}
}