Skip to content

Latest commit

 

History

History
131 lines (97 loc) · 5.3 KB

239. Sliding Window Maximum.md

File metadata and controls

131 lines (97 loc) · 5.3 KB
Raw

239. Sliding Window Maximum

思路

给定一个数组和一个窗口大小k，让窗口从左往右滑动，返回每次窗口内的数字的最大值。

思路一

此题最容易想到的就是利用插入、删除和找到最值都不算慢的数据结构，将窗口内的元素维护在这个数据结构中。所以我们可以利用类似搜索二叉树的结构，例如STL中的map、set和multiset等，但是由于有重复元素，所以我们可以用multiset。

有几个注意点：

  • multiset默认是从小到大排序，所以最大值为最后一个元素，即*st.rbegin()或*prev(st.end())；
  • 我们定义multiset的时候可以传入greater<int>类使从大到小排序，这样最大值为*st.begin()。
  • 由于有重复数字，但每次只想删除一个，而 erase(val) 是将所有val都删掉，所以我们只能提供一个迭代器，代表一个确定的删除位置，即用erase(find(val))删除。

由于插入删除都是对数级别，所以总的时间复杂度为O(nlogk)，额外的空间开辟就是multiset，为O(k)。

思路二、双向取max

当k比较大的时候思路一的时间复杂度就显得有点高了，此题还有两个O(n)复杂度的思路，即思路二和思路三。

用一个例子来说明: nums = [2,1,3,4,6,3,8,9,10,12,56], k = 4

1. 将数组根据窗口大小换分成若干块（最后一块可能不足k）：
              2, 1, 3, 4 | 6, 3, 8, 9 | 10, 12, 56

2. 从左到右记录到目前位置的最大值，注意每一块分别计算：
left_max[]  = 2, 2, 3, 4 | 6, 6, 8, 9 | 10, 12, 56

3. 类似的，从右到左记录到目前位置的最大值，注意每一块分别计算：
right_max[] = 4, 4, 4, 4 | 9, 9, 9, 9 | 56, 56, 56

4. 现在，若某个滑动窗口最右元素为nums[i]，那么这个窗口内的最大值就为 max(left_max[i], right_max[i-k+1]);

简单证明一下，根据当前窗口是否刚好落在之前划分的某一块，可分为两种情况：

  1. 若是，即(i + 1) % k == 0，那么left_max[i]和right_max[i-k+1])相等，均等于窗口内最大值；
  2. 若不是，即窗口会横跨某相邻两块的交界线，这个交界线将窗口划分成左右两个部分，left_max[i]即右部分最大值而right_max[i-k+1])为左部分最大值。

时间复杂度O(n)，空间复杂度O(n)

思路三、单调队列

还有一个O(n)的比较难想的思路，需要用到双向队列deque。

核心思想是我们不把窗口内所有元素都送入deque而是只将有可能成为最大值的元素（的下标）送入deque。从左往右滑动窗口，若窗口即将把nums[i]包含进来，

  1. 首先，若队首元素下标小于i - k，即在窗口之外了，所以应该删除队首元素；
  2. 然后，由于我们仅保留有可能成为最大值的元素（的下标），所以我们应该从队尾开始不断去掉比nums[i]小的那些元素（的下标），因为只要窗口内有nums[i]，那么去掉的这些元素就不可能成为最大值。
  3. 最后，我们将nums[i]（的下标）送入队尾。

因此，按照上述过程维护的队列里面的元素是单调递减的，队首的元素即每次窗口内的最大值。

这里需要掌握几个修改deque的操作：

  • push_back：从队尾加入队列；
  • push_front：从队首加入队列；
  • pop_back：删除队尾元素；
  • pop_front：删除队首元素。

时间复杂度O(n)，空间复杂度O(n)

C++

思路一

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        if(nums.empty()) return {};
        int n = nums.size();
        vector<int>res(n - k + 1);
        
        multiset<int>st; // 从小到大排序
        //multiset<int, greater<int>>st; // 从大到小排序
        
        for(int i = 0, j = 0; i < n; i++){
            if(i >= k) st.erase(st.find(nums[i-k])); // 不能st.erase(nums[i-k])
            st.insert(nums[i]);
            if(i >= k-1) res[j++] = *prev(st.end()); // 或st.rbegin()
        }
        
        return res;
    }
};

思路二

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        if(nums.empty()) return {};
        int n = nums.size();
        vector<int>res(n - k + 1);
        vector<int>left_max(n), right_max(n);
        
        int maximum = INT_MIN;
        for(int i = 0; i < n; i++)
            left_max[i] = maximum = (i % k == 0) ? nums[i] : max(maximum, nums[i]);
        
        maximum = nums.back();
        for(int i = n-1; i >= 0; i--)
            right_max[i] = maximum = ((i + 1) % k == 0) ? nums[i] : max(maximum, nums[i]);
        
        for(int i = k-1, j = 0; i < n; i++)
            res[j++] = max(left_max[i], right_max[i-k+1]);
        
        return res;
    }
};

思路三

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        vector<int>res;
        deque<int>win;

        for(int i = 0; i < nums.size(); i++){
            if (!win.empty() && win.front() == i - k) win.pop_front();
            
            while(!win.empty() && nums[win.back()] <= nums[i]) win.pop_back();
            
            win.push_back(i);
            
            if(i >= k - 1) res.push_back(nums[win.front()]);
        }
        return res;
    }
};