剑指 Offer 59 - I. 滑动窗口的最大值

系统管理员 2022-10-27 01:39 108阅读 0赞

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zODE5OTc3MA_size_16_color_FFFFFF_t_70]  
[题解][Link 1]

//解法一：单调队列
    //单调队列写法一
    class Solution {
        
        public int[] maxSlidingWindow(int[] nums, int k) {
        
            if(nums == null || nums.length<k || k<1){
        
                return new int[0];
            }
            //#1
            LinkedList<Integer> queue = new LinkedList<>();
            int[] result = new int[nums.length - k + 1];
            int index = 0;
            for(int i = 0; i<nums.length; i++){
        
    
                //#2
                while(!queue.isEmpty() && nums[i]>=nums[queue.peekLast()]){
        
                    queue.pollLast();
                }
                queue.addLast(i);
    
                //#3 
                if(queue.peekFirst()<=(i-k)){
        //如果被窗口抛下了（在窗口左边界的左侧）
                    queue.pollFirst();
                }
                if(i>=k-1){
        
                    result[index++] = nums[queue.peekFirst()];
                }
            }
            return result;
        }
    }
    //单调队列写法二
    class Solution {
        
        public int[] maxSlidingWindow(int[] nums, int k) {
        
            int n = nums.length;
            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;
        }
    }

//解法二：优先队列
    class Solution {
        
        public int[] maxSlidingWindow(int[] nums, int k) {
        
            int n = nums.length;
            PriorityQueue<int[]> q = 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++){
        
                q.offer(new int[]{
        nums[i], i});
            }
            int[] ans = new int[n - k + 1];
            ans[0] = q.peek()[0];
            for(int i = k; i < n; i++){
        
                q.offer(new int[]{
        nums[i], i});
                while(q.peek()[1] <= i - k){
        
                    q.poll();
                }
                ans[i - k + 1] = q.peek()[0];
            }
            return ans;
        }
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zODE5OTc3MA_size_16_color_FFFFFF_t_70]: /images/20221024/b357eb4490bc49fd983c5d4f72da14cc.png
[Link 1]: https://leetcode-cn.com/problems/hua-dong-chuang-kou-de-zui-da-zhi-lcof/solution/yi-ge-shi-pin-kan-dong-dan-diao-dui-lie-1dq85/