資訊專欄INFORMATION COLUMN
摘要：題目鏈接這道題用，注意一下存的是，因?yàn)橐袛嗍欠竦阶畲蟮闹?，是通過現(xiàn)在的和第一個(gè)的差來判斷的。
Sliding Window Maximum
題目鏈接：https://leetcode.com/problems...
這道題用deque，注意一下存的是index，因?yàn)橐袛嗍欠竦阶畲蟮膚indow值，是通過現(xiàn)在的index和deque第一個(gè)index的差來判斷的。
public class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
if(nums == null || nums.length == 0 || k == 0) return new int[0];
/* result size: nums.length - k + 1
* deque: 1st element is the largest one, store the index !!
* 1. poll 1st element when 1st away from current = k
* 2. poll last element while last <= current, add current
* 3. put the 1st element into the result if index >= k - 1
*/
int[] result = new int[nums.length - k + 1];
Deque deq = new LinkedList();
for(int i = 0; i < nums.length; i++) {
// step 1
if(!deq.isEmpty() && i - deq.peek() == k) deq.poll();
// step 2
while(!deq.isEmpty() && nums[deq.peekLast()] <= nums[i]) deq.pollLast();
deq.offer(i);
// step 3
if(i - k + 1 >= 0) result[i - k + 1] = nums[deq.peek()];
}
return result;
}
}
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://www.ezyhdfw.cn/yun/66569.html
摘要：窗口前進(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...
摘要：丟棄隊(duì)首那些超出窗口長度的元素隊(duì)首的元素都是比后來加入元素大的元素，所以存儲(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...
摘要：這樣，我們可以保證隊(duì)列里的元素是從頭到尾降序的，由于隊(duì)列里只有窗口內(nèi)的數(shù)，所以他們其實(shí)就是窗口內(nèi)第一大，第二大，第三大的數(shù)。 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...
摘要：題目要求假設(shè)有一個(gè)數(shù)組和一個(gè)長度為的窗口，數(shù)組長度。當(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...
摘要：題目鏈接這題和那道比起來多加了個(gè)。還是用兩個(gè)來做，這個(gè)操作復(fù)雜度用了。和，在保存較小的一半元素，保存較大的一半元素，，注意寫的時(shí)候不能用，因?yàn)榭赡堋]想出來其他方法，參考的解法 480. Sliding Window Median 題目鏈接：https://leetcode.com/problems... 這題和那道Find Median from Data Stream比起來多加了個(gè)...
閱讀 972·2021-11-22 09:34
閱讀 1153·2021-10-08 10:16
閱讀 1923·2021-07-25 21:42
閱讀 1871·2019-08-30 15:53
閱讀 3595·2019-08-30 13:08
閱讀 2277·2019-08-29 17:30
閱讀 3428·2019-08-29 17:22
閱讀 2284·2019-08-29 15:35
