[Leetcode] Sliding Window Maximum 滑動窗口最大值

lvzishen 發布于2019-08-14 12:46 / 634人閱讀

摘要：這樣，我們可以保證隊列里的元素是從頭到尾降序的，由于隊列里只有窗口內的數，所以他們其實就是窗口內第一大，第二大，第三大的數。

Sliding Window Maximum

Given an array nums, there is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves right by one position.
For example, Given nums = [1,3,-1,-3,5,3,6,7], and k = 3.
Window position                Max
---------------               -----
[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 
Therefore, return the max sliding window as [3,3,5,5,6,7].
Note:  You may assume k is always valid, ie: 1 ≤ k ≤ input array"s size for non-empty array.
Follow up: Could you solve it in linear time?
Hint:
How about using a data structure such as deque (double-ended queue)? The queue size need not be the same as the window’s size. Remove redundant elements and the queue should store only elements that need to be considered.

優先隊列 復雜度

時間 O(NlogK) 空間 O(K)

思路

維護一個大小為K的最大堆，依此維護一個大小為K的窗口，每次讀入一個新數，都把堆中窗口最左邊的數扔掉，再把新數加入堆中，這樣堆頂就是這個窗口內最大的值。

注意

-結果數組的大小是nums.length + 1 - k，賦值時下標也是i + 1 - k

代碼

public class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        if(nums == null || nums.length == 0) return new int[0];
        PriorityQueue pq = new PriorityQueue(Collections.reverseOrder());
        int[] res = new int[nums.length + 1 - k];
        for(int i = 0; i < nums.length; i++){
            // 把窗口最左邊的數去掉
            if(i >= k) pq.remove(nums[i - k]);
            // 把新的數加入窗口的堆中
            pq.offer(nums[i]);
            // 堆頂就是窗口的最大值
            if(i + 1 >= k) res[i + 1 - k] = pq.peek();
        }
        return res;
    }
}

雙向隊列 復雜度

時間 O(N) 空間 O(K)

思路

我們用雙向隊列可以在O(N)時間內解決這題。當我們遇到新的數時，將新的數和雙向隊列的末尾比較，如果末尾比新數小，則把末尾扔掉，直到該隊列的末尾比新數大或者隊列為空的時候才住手。這樣，我們可以保證隊列里的元素是從頭到尾降序的，由于隊列里只有窗口內的數，所以他們其實就是窗口內第一大，第二大，第三大...的數。保持隊列里只有窗口內數的方法和上個解法一樣，也是每來一個新的把窗口最左邊的扔掉，然后把新的加進去。然而由于我們在加新數的時候，已經把很多沒用的數給扔了，這樣隊列頭部的數并不一定是窗口最左邊的數。這里的技巧是，我們隊列中存的是那個數在原數組中的下標，這樣我們既可以直到這個數的值，也可以知道該數是不是窗口最左邊的數。這里為什么時間復雜度是O(N)呢？因為每個數只可能被操作最多兩次，一次是加入隊列的時候，一次是因為有別的更大數在后面，所以被扔掉，或者因為出了窗口而被扔掉。

代碼

public class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        if(nums == null || nums.length == 0) return new int[0];
        LinkedList deque = new LinkedList();
        int[] res = new int[nums.length + 1 - k];
        for(int i = 0; i < nums.length; i++){
            // 每當新數進來時，如果發現隊列頭部的數的下標，是窗口最左邊數的下標，則扔掉
            if(!deque.isEmpty() && deque.peekFirst() == i - k) deque.poll();
            // 把隊列尾部所有比新數小的都扔掉，保證隊列是降序的
            while(!deque.isEmpty() && nums[deque.peekLast()] < nums[i]) deque.removeLast();
            // 加入新數
            deque.offerLast(i);
            // 隊列頭部就是該窗口內第一大的
            if((i + 1) >= k) res[i + 1 - k] = nums[deque.peek()];
        }
        return res;
    }
}

云服務器 GPU云服務器 Window窗口對象 Sliding Maximum LeetCode

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/64697.html

leetcode239. Sliding Window Maximum

摘要：題目要求假設有一個數組和一個長度為的窗口，數組長度。當窗口右滑時，會刪除下標上的值，并加入下標上的值。此時中記錄的值編程了，并返回當前的最大值為。一旦最大值失效，就從窗口中重新找一個最大值就好了。題目要求 Given an array nums, there is a sliding window of size k which is moving from the very lef...

sPeng 2019-08-15 14:22 評論0 收藏0
LeetCode 之 JavaScript 解答第239題 —— 滑動窗口最大值（Sliding W

摘要：你只可以看到在滑動窗口內的數字?；瑒哟翱诿看沃幌蛴乙苿右晃?。返回滑動窗口最大值。算法思路暴力破解法用兩個指針，分別指向窗口的起始位置和終止位置，然后遍歷窗口中的數據，求出最大值向前移動兩個指針，然后操作，直到遍歷數據完成位置。 Time：2019/4/16Title: Sliding Window MaximumDifficulty: DifficultyAuthor: 小鹿題目...

spacewander 2019-08-23 16:59 評論0 收藏0
[LeetCode] 239. Sliding Window Maximum

摘要：丟棄隊首那些超出窗口長度的元素隊首的元素都是比后來加入元素大的元素，所以存儲的對應的元素是從小到大 Problem Given an array nums, there is a sliding window of size k which is moving from the very left of the array to the very right. You can only...

lentoo 2019-08-16 13:45 評論0 收藏0
[LintCode/LeetCode] Sliding Window Maximum/Median

摘要：窗口前進，刪隊首元素保證隊列降序加入當前元素下標從開始，每一次循環都將隊首元素加入結果數組 Sliding Window Maximum Problem Given an array of n integer with duplicate number, and a moving window(size k), move the window at each iteration fro...

crelaber 2019-08-14 14:33 評論0 收藏0
Sliding Window Maximum

摘要：題目鏈接這道題用，注意一下存的是，因為要判斷是否到最大的值，是通過現在的和第一個的差來判斷的。 Sliding Window Maximum 題目鏈接：https://leetcode.com/problems... 這道題用deque，注意一下存的是index，因為要判斷是否到最大的window值，是通過現在的index和deque第一個index的差來判斷的。 public cla...

mrcode 2019-08-14 17:20 評論0 收藏0