面试题59 - I. 滑动窗口的最大值

墨蓝 2023-02-18 01:56 10阅读 0赞

### 面试题59 - I. 滑动窗口的最大值 ###

*  面试题59 - I. 滑动窗口的最大值
 *   *  算法思想
     *  思路
     *  实现

# 面试题59 - I. 滑动窗口的最大值 #

题目链接：https://leetcode-cn.com/problems/hua-dong-chuang-kou-de-zui-da-zhi-lcof/

## 算法思想 ##

滑动窗口、双端队列

## 思路 ##

我们维护一个单调的双向队列，窗口在每次滑动的时候，我就从队列头部取当前窗口中的最大值，每次窗口新进来一个元素的时候，我就将它与队列中的元素进行大小比较：

*  如果刚刚进来的元素比队列的尾部元素大，那么先将队列尾部的元素弹出，然后把刚刚进来的元素添到队列的尾部；
 *  如果刚刚进来的元素比队列的尾部元素小，那么把刚刚进来的元素直接添到队列的尾部即可。

需要注意的是:  
当还没有形成窗口的时候的处理：

1.  单独使用循环，让队列形成第一个窗口。
2.  在循环中判断是否形成窗口  
    当滑动窗口已经略过队列头部中的元素：  
    在循环时要判断队列头部元素与窗口之前的那个元素是否相等，如果相等将头部弹出。

## 实现 ##

import java.util.Deque;
    import java.util.LinkedList;
    
    class MaxSlidingWindow { 
        /** * 有单调双端队列来维护一个单调的线性队列。 队列的头部元素就是最大的元素。 * * 空间复杂度O(n) 时间复杂度O(n) * @param nums * @param k * @return */
        public int[] maxSlidingWindow(int[] nums, int k) { 
            if (nums == null || k <= 0 || nums.length < k) { 
    
                return new int[0];
            }
            // 初始化参数
            int[] res = new int[nums.length - k + 1];
            Deque<Integer> deque = new LinkedList<>();
            int index = 0;
            for (int i = 0; i < nums.length; i++) { 
    
                // 在队列不为空的情况下，如果队列尾部的元素要比当前的元素小，或等于当前的元素
                // 那么为了维持从大到小的原则，我必须让尾部元素弹出
                while (!deque.isEmpty() && nums[deque.peekLast()] < nums[i]) { 
                    deque.removeLast();
                }
    
                deque.addLast(i);
                // 如果滑动窗口已经略过了队列中头部的元素，则将头部元素弹出
    
                if (deque.peekFirst() == i - k) { 
                    deque.removeFirst();
                }
                // 看看窗口有没有形成，只有形成了大小为 k 的窗口，我才能收集窗口内的最大值
                if (i >= (k - 1)) { 
                    res[index++] = nums[deque.peekFirst()];
                }
    
            }
            return res;
        }
    
        public int[] maxSlidingWindow1(int[] nums, int k) { 
            if (nums == null || k <= 0 || nums.length < k) { 
                return new int[0];
            }
            // 初始化参数
            int[] res = new int[nums.length - k + 1];
            Deque<Integer> deque = new LinkedList<>();
            int index = 0;
            // 让队列形成窗口
            for (int i = 0; i < k; i++) { 
                while (!deque.isEmpty() && deque.peekLast() < nums[i]) { 
                    deque.removeLast();
                }
                deque.addLast(nums[i]);
            }
    
            res[index++] = deque.peekFirst();
            for (int i = k; i < nums.length; i++) { 
                // 如果滑动窗口已经略过了队列中头部的元素，则将头部元素弹出
                if (deque.peekFirst() == nums[i - k]) { 
                    deque.removeFirst();
                }
                // 在队列不为空的情况下，如果队列尾部的元素要比当前的元素小，或等于当前的元素
                // 那么为了维持从大到小的原则，我必须让尾部元素弹出
                while (!deque.isEmpty() && deque.peekLast() < nums[i]) { 
                    deque.removeLast();
                }
                deque.addLast(nums[i]);
                res[index++] = deque.peekFirst();
    
            }
            return res;
        }
    
    }