剑指offer-64、滑动窗⼝的最⼤值

题⽬描述

给定⼀个数组和滑动窗⼝的⼤⼩，找出所有滑动窗⼝⾥数值的最⼤值。例如，如果输⼊数组 {2,3,4,2,6,2,5,1} 及滑动窗⼝的⼤⼩ 3 ，那么⼀共存在 6 个滑动窗⼝，他们的最⼤值分别为 {4,4,6,6,6,5} ；
针对数组 {2,3,4,2,6,2,5,1} 的滑动窗⼝有以下6个： {[2,3,4],2,6,2,5,1} ， {2,[3,4,2],6,2,5,1} ， {2,3,[4,2,6],2,5,1} ， {2,3,4, [2,6,2],5,1} ， {2,3,4,2,[6,2,5],1} ， {2,3,4,2,6,[2,5,1]} 。 窗⼝⼤于数组⻓度的时候，返回空。
思路及解答

暴力法

遍历每个可能的窗口起始位置，计算窗口内的最大值

1. public class Solution {
2.     public int[] maxSlidingWindow(int[] nums, int k) {
3.         // 处理边界情况
4.         if (nums == null || nums.length == 0 || k <= 0 || k > nums.length) {
5.             return new int[0];
6.         }
7.         
8.         int n = nums.length;
9.         int[] result = new int[n - k + 1]; // 结果数组
10.         
11.         // 遍历每个窗口的起始位置
12.         for (int i = 0; i <= n - k; i++) {
13.             int max = Integer.MIN_VALUE;
14.             
15.             // 计算当前窗口内的最大值
16.             for (int j = i; j < i + k; j++) {
17.                 if (nums[j] > max) {
18.                     max = nums[j];
19.                 }
20.             }
21.             result[i] = max;
22.         }
23.         
24.         return result;
25.     }
26. }

复制代码

• 时间复杂度：O(n×k)，需要处理n-k+1个窗口，每个窗口需要k次比较
  
• 空间复杂度：O(1)，除结果数组外只使用常数空间
  

双端队列法（最优解）

⾸先进⾏⾮空判断，以及数组⻓度是否不为 0 ，是否不⼩于窗⼝⻓度。
其次，使⽤⼀个双向链表，⾥⾯保存的是索引，遍历每⼀个元素，如果双向队列不为空且最后的元素作为索引的数值⼩于当前的元素，就把当前的元素的索引加到队列的后⾯。（这样可以保证队列从头到尾是单调递减的，也就是队尾的元素就是最⼩的元素）。
然后把当前的元素加进去队列尾部。判断队列前⾯的元素是不是索引位置不符合，如果不符合，就移除队列头部的元素。
那么此时的队列⾸部肯定就是滑动窗⼝的最⼤值。（此处应该判断滑动窗⼝⽣效的索引）
以 2, 3, 4, 2, 6, 2, 5, 1 为例：

所有的窗⼝最⼤值⾄此已经收集完成。

1. public class Solution64 {
2.      public static void main(String[] args) {
3.          int[] nums = {2, 3, 4, 2, 6, 2, 5, 1};
4.          System.out.println(new Solution64().maxInWindows(nums, 3));
5.      }
6.    
7.      public ArrayList<Integer> maxInWindows(int[] num, int size) {
8.          ArrayList<Integer> results = new ArrayList<>();
9.          if (num == null || num.length == 0 || num.length < size || size <= 0) {
10.                  return results;
11.          }
12.          
13.          LinkedList<Integer> integers = new LinkedList<>();
14.          for (int i = 0; i < num.length; i++) {
15.              while (!integers.isEmpty() && num[integers.peekLast()] < num[i]) {
16.                      integers.removeLast();
17.              }
18.              integers.addLast(i);
19.              while (i - integers.peekFirst() >= size) {
20.                      integers.removeFirst();
21.              }
22.              if (i >= size - 1) {
23.                      results.add(num[integers.peekFirst()]);
24.              }
25.          }
26.          return results;
27.      }
28. }

复制代码

• 时间复杂度：O（n）,所有的元素都进⼊队列，再出队列
  
• 空间复杂度：O(n)，使⽤额外的队列空间存储索引以及窗⼝最⼤值。
  

动态规划法（分块思想）

将数组分成大小为k的块，预处理每个位置的左右最大值
分块思想：

• 将数组划分为大小为k的块（最后一块可能不满）
  
• left：从当前块开始到位置i的最大值
  
• right：从位置i到当前块结束的最大值
  

窗口最大值计算：
对于窗口[i, i+k-1]：

• 如果窗口完全在一个块内：right或left[i+k-1]就是最大值
  
• 如果窗口跨越两个块：最大值 = max(右块的左最大值, 左块的右最大值)
  

[code]public class Solution {    public int[] maxSlidingWindow(int[] nums, int k) {        if (nums == null || nums.length == 0 || k = 0; i--) {            if ((i + 1) % k == 0) {                // 块的尾元素，重新开始计算                right = nums;            } else {                // 与后一个位置比较取最大值                right = Math.max(right[i + 1], nums);            }        }                // 计算每个窗口的最大值        for (int i = 0; i

感谢，下载保存了

不错，里面软件多更新就更好了

新版吗？好像是停更了吧。

yyds。多谢分享

前排留名，哈哈哈

分享、互助 让互联网精神温暖你我

感谢，下载保存了

前排留名，哈哈哈