HelloKenLee

Leetcode 239 Sliding Window Maximum 解题报告

Posted on By KenLee

题目信息

题目: 239. Sliding Window Maximum
难度: Hard
正确率: 32.0%
问题描述:

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

相关题目:480. Sliding Window Median

问题分析

  问题的大意是说给定一个长度为N的数组和一个窗口大小K,窗口会在数组移动,每次移动一个数。我们要求出每一次移动之前窗口内的K个数的最大值。

解题思路

  对于这个题目,最朴素的想法是一个O(N*K)的解法,其思路很简单,对于每个位置扫一次窗口,得到最大值。   但是事实上我们每一次只改变一个窗口内的元素,因此每一次窗口移动比较K个元素是很不划算的,我们稍稍改进一下可以得到一个O(N*log(K))的算法。其核心思路是我们使用一个大根堆表示窗口K。当窗口移动的时候,我们把移出窗口的元素值改为移入窗口的元素值,然后对该元素进行上升或者下降来保持堆的性质。复杂度为log(K),做N次,所以为O(N*log(K))。   最后我使用的是一个叫做单调对列的数据结构来完成一个O(N)的算法。其核心思路很简单,就是一个比较大的数进入窗口中的时候,所有在窗口中下标在他前面而且比他小的数都是没有用的,都可以被移出窗口。因此我们使用一个双向对列dequeue<int>实现该功能,双向对列存储窗口中的数的下标。每当窗口移动,我们先插入新的数,即在对列后面采用pop操作直到对列的最后一个元素比新的数大。为了模拟窗口移动的时候删除数,我们还需要对对列前的数进行处理,如果对列头的下标比当新的数在数组中的下标小k的话,表示他应该不在窗口内,把它从对列前面pop掉。

  

结果分析

  • 时间复杂度: O(N),因为每一个数最多只被push进对列一次,pop出对列一次。
  • 空间复杂度: O(K),对列的最大长度不超过K。
  • 通过时间: 66 ms
  • 击败:86.64%提交(截止到提交时间)

主要数据结构和方法

  • deque<int> dq: 一个双向对列,模拟单调对列,也就是滑动的窗口。里面存储的是元素在数组中的下标。

源代码

//单调队列
class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        deque<int> dq;//存储元素下标
        vector<int> res;
        for(int right=0;right<nums.size();++right){
            //插入操作
            while(!dq.empty() && nums[dq.back()]<nums[right]){
                dq.pop_back();
            }
            dq.push_back(right);
            //处理最大元素不在window内
            if(!dq.empty() && right-dq.front()>=k){
                dq.pop_front();
            }
            //跳过前k-1次
            if(right>=k-1)
                res.push_back(nums[dq.front()]);
        }
        return res;
    }
};