Sliding Window Maximum

mrcode 发布于2019-08-14 17:20 / 2877人阅读

摘要：题目链接这道题用，注意一下存的是，因为要判断是否到最大的值，是通过现在的和第一个的差来判断的。

Sliding Window Maximum

题目链接：https://leetcode.com/problems...

这道题用deque，注意一下存的是index，因为要判断是否到最大的window值，是通过现在的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

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/66569.html

[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
[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 滑动窗口最大值

摘要：这样，我们可以保证队列里的元素是从头到尾降序的，由于队列里只有窗口内的数，所以他们其实就是窗口内第一大，第二大，第三大的数。 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

摘要：题目要求假设有一个数组和一个长度为的窗口，数组长度。当窗口右滑时，会删除下标上的值，并加入下标上的值。此时中记录的值编程了，并返回当前的最大值为。一旦最大值失效，就从窗口中重新找一个最大值就好了。题目要求 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