239. 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 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] 7
Therefore, 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?
思考: 用maxHeap来做,每个window内都用maxheap来取得最大值。
复杂度: Time(nlogk) Space: O(k)

public static int[] maxSlidingWindow(int[] nums, int k) {
        if (nums == null || nums.length == 0) return new int[0];
        int n = nums.length;
        PriorityQueue<Integer> pq = new PriorityQueue<Integer>();
        int res[] = new int[n - k + 1];
        for (int i = 0; i < n; i++) {
            // 窗口最左边数从pq中取出
            if (i >= k) pq.remove(nums[i - k]);
            // 把新加的数放到pq
            pq.offer(nums[i]);
            // 放到结果array
            if (i + 1 >= k) res[i - k + 1] = pq.peek();

        }
        return res;
    }

复杂度:Time O(n),
思考: 不会做,参考的几个blog解答。 发现有几个总结不错的解法,受益良多。
大致上这个题目是给定一个数组num跟长度为k的window, 求window从左往右滑动过程中,在滑动窗口所见的范围k内,出现的最大值的集合。
结果集合总共有nums.length – k + 1个元素, 所以我们的数组下标对应的也就是i-k+1;
我们用一个双向队列queue在O(n)时间内解决这个问题,保持窗口内的最大值在窗口边界(队列头),实现这个方法就是不停的删除掉窗口中比新进来元素小的元素。 数组中存的是元素的坐标,而不是每个元素对应的值, 每当有新的元素进入window时候,从队队尾开始,删掉比新元素小的元素,然后将新加进来的元素放到队列末尾。这样就保证了队首元素始终是窗口(队列)最大元素.

我们对这个数组进行遍历大概有以下几个步骤:
1. 对于新加进来的元素i,我们要判断是否k-i的值等于queue中的头部的坐标, 如果等于则需要将queue中头部元素扔掉。
2. 如果queue中队尾元素对应的值小于新加的元素i对应的值,那么持续扔掉队尾元素,保证queue中元素对应的值是降序的。
3. 把i加入queue中。
4. 判断如果i+i >=k,表示至少比较了k次,则需要记录一次最大值放到最终结果里面,我们直接取queue中头部元素对应的值。

public class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        if (nums.length < k || k <= 0 || nums == null) return nums;
        Deque<Integer> queue = ArrayDeque<Integer>();
        int[] res = nums.length - k + 1;
        for (int i = 0; i < nums.length; i++) {
            // window 是往右滑动的,每当往右滑动一个数,最左边的数要拿出来,我们要检查queue中的头部的下标是否等于i-k. 
            if (!queue.isEmpty() && queue.peek() == i - k) queue.poll();
            // queue中队尾所有比新数小的都扔掉,保证queue中是降序的
            while(!queue.isEmpty() && nums[queue.peekLast()] < nums[i]) queue.pollLast();
            queue.offer(i);
            // 检查如果是比较了至少k次,那就把i-l+1这个点的坐标对应结果放到最终结果里面。
            if (i + 1 >= k) res[i-k+1] = queue.peek();
        }
        return res;
    }
}

Reference: [Leetcode] Sliding Window Maximum 滑动窗口最大值
239. Sliding Window Maximum
https://segmentfault.com/a/1190000003834593

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s