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

这篇文章介绍了剑指offer-64、滑动窗⼝的最⼤值，分享给大家做个参考，收藏Java资料网收获更多编程知识

题⽬描述

给定⼀个数组和滑动窗⼝的⼤⼩，找出所有滑动窗⼝⾥数值的最⼤值。例如，如果输⼊数组 {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]} 。 窗⼝⼤于数组⻓度的时候，返回空。

思路及解答

暴力法

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

public class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        // 处理边界情况
        if (nums == null || nums.length == 0 || k <= 0 || k > nums.length) {
            return new int[0];
        }
        
        int n = nums.length;
        int[] result = new int[n - k + 1]; // 结果数组
        
        // 遍历每个窗口的起始位置
        for (int i = 0; i <= n - k; i++) {
            int max = Integer.MIN_VALUE;
            
            // 计算当前窗口内的最大值
            for (int j = i; j < i + k; j++) {
                if (nums[j] > max) {
                    max = nums[j];
                }
            }
            result[i] = max;
        }
        
        return result;
    }
}

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

双端队列法（最优解）

⾸先进⾏⾮空判断，以及数组⻓度是否不为 0 ，是否不⼩于窗⼝⻓度。

其次，使⽤⼀个双向链表，⾥⾯保存的是索引，遍历每⼀个元素，如果双向队列不为空且最后的元素作为索引的数值⼩于当前的元素，就把当前的元素的索引加到队列的后⾯。（这样可以保证队列从头到尾是单调递减的，也就是队尾的元素就是最⼩的元素）。

然后把当前的元素加进去队列尾部。判断队列前⾯的元素是不是索引位置不符合，如果不符合，就移除队列头部的元素。

那么此时的队列⾸部肯定就是滑动窗⼝的最⼤值。（此处应该判断滑动窗⼝⽣效的索引）

以 2, 3, 4, 2, 6, 2, 5, 1 为例：

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

public class Solution64 {
     public static void main(String[] args) {
         int[] nums = {2, 3, 4, 2, 6, 2, 5, 1};
         System.out.println(new Solution64().maxInWindows(nums, 3));
     }
    
     public ArrayList<Integer> maxInWindows(int[] num, int size) {
         ArrayList<Integer> results = new ArrayList<>();
         if (num == null || num.length == 0 || num.length < size || size <= 0) {
         	return results;
         }
         
         LinkedList<Integer> integers = new LinkedList<>();
         for (int i = 0; i < num.length; i++) {
             while (!integers.isEmpty() && num[integers.peekLast()] < num[i]) {
             	integers.removeLast();
             }
             integers.addLast(i);
             while (i - integers.peekFirst() >= size) {
             	integers.removeFirst();
             }
             if (i >= size - 1) {
             	results.add(num[integers.peekFirst()]);
             }
         }
         return results;
     }
}

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

动态规划法（分块思想）

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

分块思想：

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

窗口最大值计算：

对于窗口[i, i+k-1]：

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

public class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        if (nums == null || nums.length == 0 || k <= 0) {
            return new int[0];
        }
        
        int n = nums.length;
        if (k == 1) return nums; // 窗口大小为1，直接返回原数组
        
        int[] left = new int[n];  // 从左到右的块最大值
        int[] right = new int[n]; // 从右到左的块最大值
        int[] result = new int[n - k + 1];
        
        // 构建left数组：从左到右的块内最大值
        left[0] = nums[0];
        for (int i = 1; i < n; i++) {
            if (i % k == 0) {
                // 块的首元素，重新开始计算
                left[i] = nums[i];
            } else {
                // 与前一个位置比较取最大值
                left[i] = Math.max(left[i - 1], nums[i]);
            }
        }
        
        // 构建right数组：从右到左的块内最大值
        right[n - 1] = nums[n - 1];
        for (int i = n - 2; i >= 0; i--) {
            if ((i + 1) % k == 0) {
                // 块的尾元素，重新开始计算
                right[i] = nums[i];
            } else {
                // 与后一个位置比较取最大值
                right[i] = Math.max(right[i + 1], nums[i]);
            }
        }
        
        // 计算每个窗口的最大值
        for (int i = 0; i <= n - k; i++) {
            // 窗口最大值 = max(右端点的左最大值, 左端点的右最大值)
            result[i] = Math.max(right[i], left[i + k - 1]);
        }
        
        return result;
    }
}

算法分析：

• 时间复杂度：O(n)，三次线性遍历
• 空间复杂度：O(n)，需要两个辅助数组

文章来源:https://www.cnblogs.com/sevencoding/p/19468619
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若内容造成侵权/违法违规/事实不符，请联系邮箱：jacktools123@163.com进行投诉反馈，一经查实，立即删除！