Sliding Window Maximum

mrcode 發(fā)布于2019-08-14 17:20 / 2987人閱讀

摘要：題目鏈接這道題用，注意一下存的是，因為要判斷是否到最大的值，是通過現(xiàn)在的和第一個的差來判斷的。

Sliding Window Maximum

題目鏈接：https://leetcode.com/problems...

這道題用deque，注意一下存的是index，因為要判斷是否到最大的window值，是通過現(xiàn)在的index和deque第一個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;
    }
}

GPU云服務器云服務器 Sliding Maximum window webrtc window

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

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

[LintCode/LeetCode] Sliding Window Maximum/Median

摘要：窗口前進，刪隊首元素保證隊列降序加入當前元素下標從開始，每一次循環(huán)都將隊首元素加入結果數(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...

crelaber 2019-08-14 14:33 評論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
[Leetcode] Sliding Window Maximum 滑動窗口最大值

摘要：這樣，我們可以保證隊列里的元素是從頭到尾降序的，由于隊列里只有窗口內的數(shù)，所以他們其實就是窗口內第一大，第二大，第三大的數(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...

lvzishen 2019-08-14 12:46 評論0 收藏0
leetcode239. Sliding Window Maximum

摘要：題目要求假設有一個數(shù)組和一個長度為的窗口，數(shù)組長度。當窗口右滑時，會刪除下標上的值，并加入下標上的值。此時中記錄的值編程了，并返回當前的最大值為。一旦最大值失效，就從窗口中重新找一個最大值就好了。題目要求 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
480. Sliding Window Median

摘要：題目鏈接這題和那道比起來多加了個。還是用兩個來做，這個操作復雜度用了。和，在保存較小的一半元素，保存較大的一半元素，，注意寫的時候不能用，因為可能。沒想出來其他方法，參考的解法 480. Sliding Window Median 題目鏈接：https://leetcode.com/problems... 這題和那道Find Median from Data Stream比起來多加了個...

Scorpion 2019-08-16 10:28 評論0 收藏0