浅谈【剑指offer】滑动窗口的最大值

EndlessLethe原创文章,转载请注明: 转载自小楼吹彻玉笙寒

本文链接地址: 浅谈【剑指offer】滑动窗口的最大值

题目

给定一个数组和滑动窗口的大小,找出所有滑动窗口里数值的最大值。例如,如果输入数组{2,3,4,2,6,2,5,1}及滑动窗口的大小3,那么一共存在6个滑动窗口,他们的最大值分别为{4,4,6,6,6,5}; 针对数组{2,3,4,2,6,2,5,1}的滑动窗口有以下6个: {[2,3,4],2,6,2,5,1}, {2,[3,4,2],6,2,5,1}, {2,3,[4,2,6],2,5,1}, {2,3,4,[2,6,2],5,1}, {2,3,4,2,[6,2,5],1}, {2,3,4,2,6,[2,5,1]}。

Note:题目没有说明,但是边界条件 size > num.size() or size <= 0,都需要直接返回空的vector。

四种解法

  1. 暴力,时间复杂度O(n*size)
  2. 线段树,时间复杂度O(nlogn+nlogn)
  3. 用两个优先队列,一个容纳size中的元素pq1,一个容纳已滑动删除的元素pq2。每次滑动时,看当前元素t和pq1.top()的大小,如果相等,则弹出,否则加入pq2。时间复杂度为O(n logn)
  4. 维护一个单调队列,单调队列模板题,维护滑动区间的区间最值。时间复杂度O(n)

不会单调队列的可以戳”单调队列和单调栈详解

实现代码

单调队列 O(n)

class Solution {
public:
    vector<int> maxInWindows(const vector<int>& num, unsigned int size)
    {
    vector<int> res;
    if (size > num.size()) return res;
    if (size <= 0) return res;

    int mq[100000] = {0}; 
    int l = 0, r = 0;
    // mq[0]不储存值 mq[r]为当前队列的最后一个 
    // 因为是维护最大值,所以需要单调递减的队列 
    for (int i = 0; i < size; i++) {
        while (l < r && mq[r] < num[i]) --r;
        mq[++r] = num[i];
    }
       res.push_back(mq[l+1]);
       for (int i = size; i < num.size(); i++) {
            if (l < r && num[i-size] == mq[l+1]) l++;
            while (l < r && mq[r] < num[i]) --r;
            mq[++r] = num[i];
            res.push_back(mq[l+1]);
        }
    return res;
   }
};

优先队列 O(nlogn)

class Solution {
public:
    vector<int> maxInWindows(const vector<int>& num, unsigned int size)
    {
    vector<int> res;
    if (size > num.size()) return res;
    if (size <= 0) return res;
   priority_queue<int> pq1, pq2; 

    for (int i = 0; i < size; i++) {
        pq1.push(num[i]);
    }
    res.push_back(pq1.top());
//        printf("%d\n", num.size());
    for (int i = size; i < num.size(); i++) {
//          printf("i %d pq1.size %d pq1.top %d\n", i, pq1.size(), pq1.top());
        if (num[i-size] == pq1.top()) {
           pq1.pop();
            // 先删后加,让pq2尽可能小一点
            while (!pq2.empty() && pq2.top() == pq1.top()) {
                pq2.pop();
                pq1.pop();
            }
        }
        else {
            pq2.push(num[i-size]);
        }
        pq1.push(num[i]);
        res.push_back(pq1.top());
//            printf("add %d\n", pq1.top());
    }
    return res;
    }
};

发表评论

电子邮件地址不会被公开。 必填项已用*标注