【leetcode】239. 滑动窗口最大值

题目内容

239. 滑动窗口最大值

思路分析

参考资料

方法一：优先队列

似乎这种最大值问题比较容易想到优先队列这种数据类型，优先队列可以维护一个最大或最小值，一般是由二叉堆实现的。关于二叉堆我专门写了一篇学习笔记。

优先队列可以自动帮我们得出前i个数的最大值，然而这个题目是个窗口问题，因此每次判断队列的最大值的下标是否在窗口内，若不在则不断弹出最大值直至最大值下标在窗口内，若不在则将其加入答案数组，即可解决窗口带来的难题。

在具体实现时，优先队列中存储的是nums[i]的下标和对应的值。如果只存下标则无法利用优先队列进行排序，若只存对应的值则定位到下标又需要O(n)的时间复杂度。

方法二：单调队列

这个资料里说的大体重压扁的说法我觉得还挺生动的。

单调队列也可以维护一个最值。由于我们只需要最大值，遍历数组时，依次从队尾插入元素，若后来来的数字大于等于之前的数字，则证明之前的数字没用了，可以移除掉。这样这个队列就一定变成了队头大于队尾的单调队列，即队头的元素一定是最大的。

						 |
					  |	 |
				   |  |  |
				|  |  |  |
			 |  |  |  |  |
		     |  |  |  |  |
		  |  |  |  |  |  |
数组下标   0  1  2  3  4  5

针对窗口问题，与上一题类似，需要判断队头元素是否在窗口内，若不在则不断弹出队头元素直至队头元素下标在窗口内，若不在则将其加入答案数组。

由于需要在队尾添加删除元素，队头删除元素，因此很自然地采用双向队列来实现单调队列。

在具体实现时，在单调队列中存储数组的下标即可。

代码

#include <vector>
#include <math.h>
#include <limits.h>
#include <queue>
#include <deque>

using namespace std;

// 优先队列法
// 时间复杂度O(nlogn)
// 空间复杂度O(n)
class Solution1 {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
      int n = nums.size();
      k = min(n, k); // 防止k比n大的情况

      priority_queue <pair<int, int>> q;
      vector<int> result;

      for (int i = 0; i < k; ++i) {
         q.emplace(make_pair(nums[i],i));
      }
      result.push_back(q.top().first);

      for (int i = k; i < n; ++i) {
         q.emplace(make_pair(nums[i], i));

         while ( q.top().second <= i - k ) {
            q.pop();
         }

         result.push_back(q.top().first);
      }

      return result;
    }
};

// 单调队列法
// 时间复杂度O(n)，每个元素被放入队列一次，且最多被弹出一次
// 空间复杂度O(k)，队列中最多不超过k+1个元素
class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
      int n = nums.size();
      k = min(k, n);
      
      deque<int> dq;
      vector<int> result; 

      for (int i = 0; i < k; ++i) {
         while (!dq.empty() && nums[dq.back()] <= nums[i]) {
                  dq.pop_back(); // 遇到比当前数字大的数字则可以直接移除
         }
         dq.push_back(i);
      }
      result.push_back(nums[dq.front()]);

      for(int i = k; i < n; ++i) {
         while (!dq.empty() && nums[dq.back()] <= nums[i]) {
            dq.pop_back(); // 遇到比当前数字大的数字则可以直接移除
         }
         dq.push_back(i);
         while (dq.front() <= i - k) {
            dq.pop_front(); // 如果队首数字不在窗口内，则移除
         }
         result.push_back(nums[dq.front()]);
      }

      return result;
    }
};

int main()
{
   Solution s;
   vector<int> input{1,3,-1,-3,5,3,6,7};
   int k = 3;
   vector<int> result;
   result = s.maxSlidingWindow(input, k);
   int a = 0;
}

收获

对优先队列进行了应用
学习了单调队列