資訊專欄INFORMATION COLUMN
摘要：這樣，我們可以保證隊(duì)列里的元素是從頭到尾降序的，由于隊(duì)列里只有窗口內(nèi)的數(shù)，所以他們其實(shí)就是窗口內(nèi)第一大，第二大，第三大的數(shù)。
Sliding Window Maximum
優(yōu)先隊(duì)列 復(fù)雜度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] 7Therefore, 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.
時(shí)間 O(NlogK) 空間 O(K)
思路維護(hù)一個(gè)大小為K的最大堆，依此維護(hù)一個(gè)大小為K的窗口，每次讀入一個(gè)新數(shù)，都把堆中窗口最左邊的數(shù)扔掉，再把新數(shù)加入堆中，這樣堆頂就是這個(gè)窗口內(nèi)最大的值。
注意-結(jié)果數(shù)組的大小是nums.length + 1 - k， 賦值時(shí)下標(biāo)也是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++){
// 把窗口最左邊的數(shù)去掉
if(i >= k) pq.remove(nums[i - k]);
// 把新的數(shù)加入窗口的堆中
pq.offer(nums[i]);
// 堆頂就是窗口的最大值
if(i + 1 >= k) res[i + 1 - k] = pq.peek();
}
return res;
}
}
雙向隊(duì)列
復(fù)雜度
時(shí)間 O(N) 空間 O(K)
思路我們用雙向隊(duì)列可以在O(N)時(shí)間內(nèi)解決這題。當(dāng)我們遇到新的數(shù)時(shí)，將新的數(shù)和雙向隊(duì)列的末尾比較，如果末尾比新數(shù)小，則把末尾扔掉，直到該隊(duì)列的末尾比新數(shù)大或者隊(duì)列為空的時(shí)候才住手。這樣，我們可以保證隊(duì)列里的元素是從頭到尾降序的，由于隊(duì)列里只有窗口內(nèi)的數(shù)，所以他們其實(shí)就是窗口內(nèi)第一大，第二大，第三大...的數(shù)。保持隊(duì)列里只有窗口內(nèi)數(shù)的方法和上個(gè)解法一樣，也是每來(lái)一個(gè)新的把窗口最左邊的扔掉，然后把新的加進(jìn)去。然而由于我們?cè)诩有聰?shù)的時(shí)候，已經(jīng)把很多沒(méi)用的數(shù)給扔了，這樣隊(duì)列頭部的數(shù)并不一定是窗口最左邊的數(shù)。這里的技巧是，我們隊(duì)列中存的是那個(gè)數(shù)在原數(shù)組中的下標(biāo)，這樣我們既可以直到這個(gè)數(shù)的值，也可以知道該數(shù)是不是窗口最左邊的數(shù)。這里為什么時(shí)間復(fù)雜度是O(N)呢？因?yàn)槊總€(gè)數(shù)只可能被操作最多兩次，一次是加入隊(duì)列的時(shí)候，一次是因?yàn)橛袆e的更大數(shù)在后面，所以被扔掉，或者因?yàn)槌隽舜翱诙蝗拥簟?/p> 代碼
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++){
// 每當(dāng)新數(shù)進(jìn)來(lái)時(shí)，如果發(fā)現(xiàn)隊(duì)列頭部的數(shù)的下標(biāo)，是窗口最左邊數(shù)的下標(biāo)，則扔掉
if(!deque.isEmpty() && deque.peekFirst() == i - k) deque.poll();
// 把隊(duì)列尾部所有比新數(shù)小的都扔掉，保證隊(duì)列是降序的
while(!deque.isEmpty() && nums[deque.peekLast()] < nums[i]) deque.removeLast();
// 加入新數(shù)
deque.offerLast(i);
// 隊(duì)列頭部就是該窗口內(nèi)第一大的
if((i + 1) >= k) res[i + 1 - k] = nums[deque.peek()];
}
return res;
}
}
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://www.ezyhdfw.cn/yun/64697.html
摘要：題目要求假設(shè)有一個(gè)數(shù)組和一個(gè)長(zhǎng)度為的窗口，數(shù)組長(zhǎng)度。當(dāng)窗口右滑時(shí)，會(huì)刪除下標(biāo)上的值，并加入下標(biāo)上的值。此時(shí)中記錄的值編程了，并返回當(dāng)前的最大值為。一旦最大值失效，就從窗口中重新找一個(gè)最大值就好了。 題目要求 Given an array nums, there is a sliding window of size k which is moving from the very lef...
摘要：你只可以看到在滑動(dòng)窗口內(nèi)的數(shù)字?；瑒?dòng)窗口每次只向右移動(dòng)一位。返回滑動(dòng)窗口最大值。算法思路暴力破解法用兩個(gè)指針，分別指向窗口的起始位置和終止位置，然后遍歷窗口中的數(shù)據(jù)，求出最大值向前移動(dòng)兩個(gè)指針，然后操作，直到遍歷數(shù)據(jù)完成位置。 Time：2019/4/16Title: Sliding Window MaximumDifficulty: DifficultyAuthor: 小鹿 題目...
摘要：丟棄隊(duì)首那些超出窗口長(zhǎng)度的元素隊(duì)首的元素都是比后來(lái)加入元素大的元素，所以存儲(chǔ)的對(duì)應(yīng)的元素是從小到大 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...
摘要：窗口前進(jìn)，刪隊(duì)首元素保證隊(duì)列降序加入當(dāng)前元素下標(biāo)從開始，每一次循環(huán)都將隊(duì)首元素加入結(jié)果數(shù)組 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...
摘要：題目鏈接這道題用，注意一下存的是，因?yàn)橐袛嗍欠竦阶畲蟮闹?，是通過(guò)現(xiàn)在的和第一個(gè)的差來(lái)判斷的。 Sliding Window Maximum 題目鏈接：https://leetcode.com/problems... 這道題用deque，注意一下存的是index，因?yàn)橐袛嗍欠竦阶畲蟮膚indow值，是通過(guò)現(xiàn)在的index和deque第一個(gè)index的差來(lái)判斷的。 public cla...
閱讀 3221·2023-04-26 02:27
閱讀 2950·2021-11-22 13:54
閱讀 1042·2021-11-12 10:36
閱讀 3918·2021-10-09 09:44
閱讀 3308·2021-10-09 09:41
閱讀 1437·2021-09-22 10:02
閱讀 3030·2019-08-30 15:56
閱讀 3233·2019-08-30 11:02
