[LeetCode]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.

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?

思路

如果采用蛮力法，这个问题似乎不难解决：可以扫描每一个滑动窗口的所有数字并找出其中的最大值。如果滑动窗口的大小为k，需要O(k)时间才能找出滑动窗口里的最大值。对于长度为n的输入数组，这个算法总的时间复杂度是O(nk)。
　　实际上一个滑动窗口可以看成是一个队列。当窗口滑动时，处于窗口的第一个数字被删除，同时在窗口的末尾添加一个新的数字。这符合队列的先进先出特性。如果能从队列中找出它的最大数，这个问题也就解决了。
　　我们实现了一个可以用O(1)时间得到最小值的栈。同样，也可以用O(1)时间得到栈的最大值。同时我们讨论了如何用两个栈实现一个队列。综合这两个问题的解决方法，我们发现如果把队列用两个栈实现，由于可以用O(1)时间得到栈中的最大值，那么也就可以用O(1)时间得到队列的最大值，因此总的时间复杂度也就降到了O(n)。 我们可以用这个方法来解决问题。不过这样就相当于在一轮面试的时间内要做两个面试题，时间未必够用。再来看看有没有其它的方法。
　　下面换一种思路。我们并不把滑动窗口的每个数值都存入队列中，而只把有可能成为滑动窗口最大值的数值存入到一个两端开口的队列。接着以输入数字{2,3,4,2,6,2,5,1}为例一步分析。
　　数组的第一个数字是2，把它存入队列中。第二个数字是3.由于它比前一个数字2大，因此2不可能成为滑动窗口中的最大值。2先从队列里删除，再把3存入到队列中。此时队列中只有一个数字3.针对第三个数字4的步骤类似，最终在队列中只剩下一个数字4.此时滑动窗口中已经有3个数字，而它的最大值4位于队列的头部。
　　接下来处理第四个数字2。2比队列中的数字4小。当4滑出窗口之后2还是有可能成为滑动窗口的最大值，因此把2存入队列的尾部。现在队列中有两个数字4和2，其中最大值4仍然位于队列的头部。
　　下一个数字是6.由于它比队列中已有的数字4和2都大，因此这时4和2已经不可能成为滑动窗口中的最大值。先把4和2从队列中删除，再把数字6存入队列。这个时候最大值6仍然位于队列的头部。
　　第六个数字是2.由于它比队列中已有的数字6小，所以2也存入队列的尾部。此时队列中有两个数字，其中最大值6位于队列的头部。
　　接下来的数字是5.在队列中已有的两个数字6和2里，2小于5，因此2不可能是一个滑动窗口的最大值，可以把它从队列的尾部删除。删除数字2之后，再把数字5存入队列。此时队列里剩下两个数字6和5，其中位于队列头部的是最大值6.
　　数组最后一个数字是1，把1存入队列的尾部。注意到位于队列头部的数字6是数组的第5个数字，此时的滑动窗口已经不包括这个数字了，因此应该把数字6从队列删除。那么怎么知道滑动窗口是否包括一个数字？应该在队列里存入数字在数组里的下标，而不是数值。当一个数字的下标与当前处理的数字的下标之差大于或者等于滑动窗口的大小时，这个数字已经从滑动窗口中滑出，可以从队列中删除了。

代码

/*---------------------------------------
*   日期：2015-07-19
*   作者：SJF0115
*   题目: 239.Sliding Window Maximum
*   网址：https://leetcode.com/problems/sliding-window-maximum/
*   结果：AC
*   来源：LeetCode
*   博客：
-----------------------------------------*/
#include <iostream>
#include <vector>
#include <deque>
using namespace std;

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        vector<int> result;
        int size = nums.size();
        if(size <= 0 || k <= 0){
            return result;
        }//if
        // 双向队列
        deque<int> deque;
        for(int i = 0;i < k-1;++i){
            // 删除小于等于当前元素的值 例如 4 2 1 5
            while(!deque.empty() && nums[i] >= nums[deque.back()]){
                deque.pop_back();
            }//while
            deque.push_back(i);
        }//for
        // 不足k个
        if(size < k){
            result.push_back(nums[deque.front()]);
        }//if
        for(int i = k-1;i < size;++i){
            // 删除小于等于当前元素的值
            while(!deque.empty() && nums[i] >= nums[deque.back()]){
                deque.pop_back();
            }//while
            // 不在滑动窗口之内
            while(!deque.empty() && i - deque.front() >= k){
                deque.pop_front();
            }//while
            deque.push_back(i);
            result.push_back(nums[deque.front()]);
        }//for
        return result;
    }
};

int main(){
    Solution s;
    int k = 3;
    vector<int> vec = {4,1,3};//,-1,-2,-3,5,3,6,7
    vector<int> result = s.maxSlidingWindow(vec,k);
    for(int i = 0;i < result.size();++i){
        cout<<result[i]<<" ";
    }//for
    cout<<endl;
    return 0;
}

<script type="text/javascript"> $(function () { $('pre.prettyprint code').each(function () { var lines = $(this).text().split('\n').length; var $numbering = $('<ul/>').addClass('pre-numbering').hide(); $(this).addClass('has-numbering').parent().append($numbering); for (i = 1; i <= lines; i++) { $numbering.append($('<li/>').text(i)); }; $numbering.fadeIn(1700); }); }); </script>