[LintCode/LeetCode] Sliding Window Maximum/Median

crelaber 发布于2019-08-14 14:33 / 2573人阅读

摘要：窗口前进，删队首元素保证队列降序加入当前元素下标从开始，每一次循环都将队首元素加入结果数组

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 from the start of the array, find the maximum number inside the window at each moving.

Example

For array [1, 2, 7, 7, 8], moving window size k = 3. return [7, 7, 8]

At first the window is at the start of the array like this

[|1, 2, 7| ,7, 8] , return the maximum 7;

then the window move one step forward.

[1, |2, 7 ,7|, 8], return the maximum 7;

then the window move one step forward again.

[1, 2, |7, 7, 8|], return the maximum 8;

Challenge

o(n) time and O(k) memory

Solution

public class Solution {
    public ArrayList maxSlidingWindow(int[] nums, int k) {
        Deque dq = new ArrayDeque<>();
        ArrayList res = new ArrayList<>();
        for (int i = 0; i < nums.length; i++) {
            if (!dq.isEmpty() && dq.peekFirst() <= i-k) dq.pollFirst(); //窗口前进，删队首元素
            while (!dq.isEmpty() && nums[dq.peekLast()] < nums[i]) dq.pollLast(); //保证队列降序
            dq.offerLast(i); //加入当前元素下标
            if (i >= k-1) res.add(nums[dq.peekFirst()]); //从k-1开始，每一次循环都将队首元素加入结果数组
        }
        return res;
    }
}

Sliding Window Median Problem

Given an array of n integer, and a moving window(size k), move the window at each iteration from the start of the array, find the median of the element inside the window at each moving. (If there are even numbers in the array, return the N/2-th number after sorting the element in the window. )

Example

For array [1,2,7,8,5], moving window size k = 3. return [2,7,7]

At first the window is at the start of the array like this

[ | 1,2,7 | ,8,5] , return the median 2;

then the window move one step forward.

[1, | 2,7,8 | ,5], return the median 7;

then the window move one step forward again.

[1,2, | 7,8,5 | ], return the median 7;

Challenge

O(nlog(n)) time

Solution

http://www.jiuzhang.com/solut...

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

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

[LintCode/LeetCode] Minimum Window Substring

Problem Given a string source and a string target, find the minimum window in source which will contain all the characters in target. Notice If there is no such window in source that covers all charac...

Corwien 2019-08-14 15:43 评论0 收藏0
[LintCode/LeetCode] Word Break

Problem Given a string s and a dictionary of words dict, determine if s can be break into a space-separated sequence of one or more dictionary words. Example Given s = lintcode, dict = [lint, code]. R...

dunizb 2019-08-14 15:30 评论0 收藏0
[LeetCode] 480. Sliding Window Median

摘要：存大于的数存小于的数保证总比的相等或多一个元素 Problem Median is the middle value in an ordered integer list. If the size of the list is even, there is no middle value. So the median is the mean of the two middle valu...

freecode 2019-08-16 14:01 评论0 收藏0
[LintCode/LeetCode] First Unique Character in a S

Problem Given a string, find the first non-repeating character in it and return its index. If it doesnt exist, return -1. Example Given s = lintcode, return 0. Given s = lovelintcode, return 2. Tags A...

Xufc 2019-08-15 13:27 评论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