LeetCode239. 滑动窗口最大值

àì夳堔傛蜴生んèń 2023-06-30 05:27 28阅读 0赞

题目描述：  
给定一个数组 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 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

**解析：**  
第一种方法：  
首先确定新数组的大小，就是nums.length-k+1,  
然后是两层for循环，解决，第一层for循环是滑动窗口的大小，第二层for循环是在滑动窗口内确定最大值。  
时间复杂度：O（mn）,空间复杂度O (1)

class Solution { 
        public int[] maxSlidingWindow(int[] nums, int k) { 
            int length = nums.length - k + 1;
            int[] array = new int[length];
            if(nums.length < k || nums == null || k < 1){ 
                return nums;
            }
            int max = 0;
            for(int i = 0; i < length; i++){ 
                int curr = i + k;
                max = nums[i];
                for(int j = i; j < curr; j++){ 
                    if(max < nums[j]){ 
                        max = nums[j];
                    }
                }
                array[i] = max;
            }
            return array;
        }
    }

第二种方法：  
借助双向队列的特点，两端都可以进行进和出。  
时间复杂度是O(n)，空间复杂度O(n).  
思路  
遍历数组，将数存放在双向队列中，并用L,R来标记窗口的左边界和右边界。队列中保存的并不是真的数，而是该数值对应的数组下标位置，并且数组中的数要从大到小排序。如果当前遍历的数比队尾的值大，则需要弹出队尾值，直到队列重新满足从大到小的要求。刚开始遍历时，L和R都为0，有一个形成窗口的过程，此过程没有最大值，L不动，R向右移。当窗口大小形成时，L和R一起向右移，每次移动时，判断队首的值的数组下标是否在\[L,R\]中，如果不在则需要弹出队首的值，当前窗口的最大值即为队首的数。

示例  
输入: nums = \[1,3,-1,-3,5,3,6,7\], 和 k = 3  
输出: \[3,3,5,5,6,7\]

解释过程中队列中都是具体的值，方便理解，具体见代码。  
初始状态：L=R=0,队列:\{\}  
i=0,nums\[0\]=1。队列为空,直接加入。队列：\{1\}  
i=1,nums\[1\]=3。队尾值为1，3>1，弹出队尾值，加入3。队列：\{3\}  
i=2,nums\[2\]=-1。队尾值为3，-1<3，直接加入。队列：\{3,-1\}。此时窗口已经形成，L=0,R=2，result=\[3\]  
i=3,nums\[3\]=-3。队尾值为-1，-3<-1，直接加入。队列：\{3,-1,-3\}。队首3对应的下标为1，L=1,R=3，有效。result=\[3,3\]  
i=4,nums\[4\]=5。队尾值为-3，5>-3，依次弹出后加入。队列：\{5\}。此时L=2,R=4，有效。result=\[3,3,5\]  
i=5,nums\[5\]=3。队尾值为5，3<5，直接加入。队列：\{5,3\}。此时L=3,R=5，有效。result=\[3,3,5,5\]  
i=6,nums\[6\]=6。队尾值为3，6>3，依次弹出后加入。队列：\{6\}。此时L=4,R=6，有效。result=\[3,3,5,5,6\]  
i=7,nums\[7\]=7。队尾值为6，7>6，弹出队尾值后加入。队列：\{7\}。此时L=5,R=7，有效。result=\[3,3,5,5,6,7\]

class Solution { 
        public int[] maxSlidingWindow(int[] nums, int k) { 
            if(nums == null || nums.length < 2) return nums;
            // 双向队列 保存当前窗口最大值的数组位置 保证队列中数组位置的数值按从大到小排序
            LinkedList<Integer> queue = new LinkedList();
            // 结果数组
            int[] result = new int[nums.length-k+1];
            // 遍历nums数组
            for(int i = 0;i < nums.length;i++){ 
                // 保证从大到小 如果前面数小则需要依次弹出，直至满足要求
                while(!queue.isEmpty() && nums[queue.peekLast()] <= nums[i]){ 
                    queue.pollLast();
                }
                // 添加当前值对应的数组下标
                queue.addLast(i);
                // 判断当前队列中队首的值是否有效
                if(queue.peek() <= i-k){ 
                    queue.poll();   
                } 
                // 当窗口长度为k时 保存当前窗口中最大值
                if(i+1 >= k){ 
                    result[i+1-k] = nums[queue.peek()];
                }
            }
            return result;
        }
    }