乐趣区

关于c++:思维提升干货All-in6种算法解决LeetCode困难题滑动窗口最大值

为了更好的浏览体验,欢送浏览原文:
[[思维晋升 | 干货 All in]6 种算法解决 LeetCode 艰难题:滑动窗口最大值 (eriktse.com)](https://www.eriktse.com/algorithm/1039.html)

最近在 leetcode 遇到一道十分经典的题目:239. 滑动窗口最大值 – 力扣(LeetCode)

以前只会看题解用枯燥队列做,最近钻研一下发现是一道很好的题,能够帮忙咱们晋升“保护区间最值”的算法思维。

先介绍一下我解决这题所用的算法及其复杂度:

  • 枯燥队列 O(n)
  • st 表 O(nlogn)
  • 树状数组 O(n(logn)^2)
  • 多重集非法 O(nlogn)
  • 莫队 O (n sqrt{n})
  • 优先队列 O(nlogn)

首先确定一点,枯燥队列是解决这道题最好的方法,然而其余的办法的适用范围更广。

1、枯燥队列

首先能够参考几篇优良的文章:

算法学习笔记(66): 枯燥队列 – 知乎 (zhihu.com)

枯燥队列 – OI Wiki (oi-wiki.org)

我这里提几点值得注意的中央:

1. 枯燥队列中寄存的是下标,而不是元素值

2. 枯燥队列是一个双端队列,尾插前先查队头后查队尾

3. 枯燥队列保护的是元素值的枯燥性

有了这几点留神,代码就很好写了:

class Solution {
public:
    static const int maxn = 1e5 + 9;
    int a[maxn];
    deque<int> dq;
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        vector<int> res;
        int n = nums.size();
        for(int i = 1;i <= n; ++ i)a[i] = nums[i - 1];
        for(int i = 1;i <= n; ++ i)
        {int x = a[i];
            while(!dq.empty() and dq.front() < i - k + 1)dq.pop_front();
            while(!dq.empty() and x >= a[dq.back()])dq.pop_back();
            dq.push_back(i);
            if(i >= k)res.push_back(a[dq.front()]);
        }
        return res;
    }
};

我做题习惯把输出数组存一个 array,大家请勿介意。

2.st 表

st 表是一种基于 DP(动静布局)思维的算法,也算是一种数据结构吧。

st 表能够动态保护区间的最值,须要用的工夫来预处理,后能够 O(1)查问。

咱们定义 dpi 示意
示意区间的最值,在这道题里咱们认为是最大值(保护最小值同理)。看一下能不能开下,大略是 maxn * 20 的大小,能够开下。

通过定义不难发现,dpi = a[i],因为此时区间长度为 1,那么最值就是元素 a[i]自身。当 j 增大时,咱们有转移方程(具体的起因可简略自行推导,当前的文章中也会有解说):

dpi = max(dpi, dpi + 2^(j-1))

查问非常不便,办法是从两边往两头尽可能多地笼罩。假如要查问的区间是[l,r]
,那么咱们能够失去区间长度 r – l + 1,当初求一个比长度小且最大的 2 的幂,而后把左右两块取大即可。

间接看代码:

class Solution {
public:
    static const int maxn = 1e5 + 9;
    int a[maxn], st[maxn][30];//st[i][j]示意 [i, i + 2^j - 1] 的最大值
    int queMax(int l, int r)
    {int k = log(r - l + 1) / log(2);
        return max(st[l][k], st[r - (1<<k) + 1][k]);
    }
    vector<int> maxSlidingWindow(vector<int>& nums, int k)
    {memset(st, 0xcf, sizeof st);
        vector<int> res;
        int n = nums.size();
        for(int i = 1;i <= n; ++ i)a[i] = nums[i - 1];
        for(int i = 1;i <= n; ++ i)st[i][0] = a[i];
        for(int k = 1;k <= 20; ++ k)
        {for(int i = 1;i <= n and i + (1 << (k - 1)) <= n; ++ i)
            {st[i][k] = max(st[i][k - 1], st[i + (1 << (k - 1))][k - 1]);
            }
        }
 
        for(int i = 1;i + k - 1 <= n; ++ i)res.push_back(queMax(i, i + k - 1));
 
        return res;
    }
};

3、树状数组

看见树状数组可能有小朋友会感到纳闷了哦,树状数组不是保护区间和的吗?怎么还来凑“区间最值”的冷落了。

其实树状数组不仅能够保护区间和,还能够“动静保护区间最值”,然而保护的办法和区间和略有不同。这一次次要看一下代码吧,具体的原理之后再讲。

树状数组节点 t[k]保护的是区间[k – lowbit(k) + 1, k]。

树状数组次要突出的长处就是能够动静保护,然而留神在保护区间最值的时候仅可单点批改,不反对区间批改。

class Solution {
public:
    static const int maxn = 1e5 + 9;
    // 树状数组
    int a[maxn], t[maxn], n;//t[i] 示意 a[i - lowbit(i) + 1] ~ a[i]的最大值
    int lowbit(int x){return x & -x;}
 
    void update(int k, int x)// modify a[k] to x
    {a[k] = x;
        while(k <= n)
        {t[k] = x;
            for(int i = 1;i < lowbit(k); i <<= 1)t[k] = max(t[k], t[k - i]);
            k += lowbit(k);
        }
    }
 
    int queMax(int l, int r)
    {int res = a[r];// 单点查问
        while(l <= r)
        {for(;r - lowbit(r) >= l; r -= lowbit(r))res = max(res, t[r]);
            res = max(res, a[r --]);
        }
        return res;
    }
 
    vector<int> maxSlidingWindow(vector<int>& nums, int k)
    {n = nums.size();
        for(int i = 1;i <= n; ++ i)a[i] = nums[i - 1];
        vector<int> res;
        for(int i = 1;i <= n; ++ i)
        {update(i, a[i]);
            if(i >= k)res.push_back(queMax(i - k + 1, i));
        }
 
        return res;
    }
};

4、多重集非法

这种办法就非常简略粗犷了,就是保护一个一直挪动的 multiset,几乎是暴力之王。

class Solution {
public:
 
    vector<int> maxSlidingWindow(vector<int>& nums, int k)
    {
        multiset<int> st;
        vector<int> res;
        for(int i = 0;i < k; ++ i)st.insert(nums[i]);
        res.push_back(*st.rbegin());
        for(int i = k;i < nums.size(); ++ i)
        {st.erase(st.find(nums[i - k]));
            st.insert(nums[i]);
            res.push_back(*st.rbegin());
        }
 
        return res;
    }
};

5、莫队

莫队须要基于 multiset,在这道题里的劣势并不显著,因为这题的询问都是有程序的,然而能够写个莫队练个手。

莫队在解决随机区间查问问题的时候有独特的劣势,因为足够暴力,所以保护的货色能够很多很杂,比方区间和,区间最值,区间元素品种数等。

当前我会具体讲莫队的,欢送大家拜访我的集体博客:https://www.eriktse.com

在右上角留下邮箱订阅我的博客,每周更新优质的算法 / 技术 / 互联网文章!

class Solution {
public:
    static const int maxn = 1e5 + 9;
    int a[maxn], pos[maxn], ans[maxn], n;
    struct Q
    {int l, r, id;// 询问离线}q[maxn];//outline algorihm
 
    multiset<int> st;
 
    void Add(int k)// 把 a[k]退出到区间内
    {st.insert(a[k]);
    }
 
    void Del(int k)
    {st.erase(st.find(a[k]));
    }
 
    vector<int> maxSlidingWindow(vector<int>& nums, int k)
    {n = nums.size();
        for(int i = 1;i <= n; ++ i)a[i] = nums[i - 1];
        int siz = sqrt(n);
        for(int i = 1;i <= n; ++ i)pos[i] = i / siz;
        int m = n - k + 1;
        for(int i = 1;i <= m; ++ i)q[i].l = i, q[i].r = i + k - 1, q[i].id = i;
 
        sort(q + 1, q + 1 + m, [this](const Q &u, const Q &v)
        {return pos[u.l] == pos[v.l] ? u.r < v.r : pos[u.l] < pos[v.l];
        });
        int L = 1, R = 0;// 以后区间
        for(int i = 1;i <= m; ++ i)
        {//[L, R] -> [l, r]
            int l = q[i].l, r = q[i].r, id = q[i].id;
            while(L < l)Del(L ++);
            while(L > l)Add(-- L);
            while(R > r)Del(R --);
            while(R < r)Add(++ R);
            ans[id] = *st.rbegin();}
        vector<int> res;
        for(int i = 1;i <= m; ++ i)res.push_back(ans[i]);
        return res;
    }
};

6、优先队列

优先队列能够了解为一个“堆”构造。

咱们晓得优先队列能够保护最值,然而他只有一个堆顶怎么办呢?

咱们只能保障堆顶是最大值然而却无奈保障堆顶是在窗口内的呀!

为了解决这个问题,咱们在每一次查问堆顶之前,都要对堆顶进行查看,直到堆顶在窗口内能力输入。

留神以下几点:

1. 堆里寄存的是下标,然而比拟函数用值比拟。

2. 每次取出元素之前堆顶查看,只有堆顶的地位不在窗口内就始终弹出。

上代码!

const int maxn = 1e5 + 9;
int a[maxn];
class Solution {
public:
    struct cmp{bool operator ()(const int &u, const int &v)const
        {return a[u] < a[v];
        }
    };
    priority_queue<int, vector<int>, cmp> pq;
    vector<int> maxSlidingWindow(vector<int>& nums, int k)
    {int n = nums.size();
        for(int i = 1;i <= n; ++ i)a[i] = nums[i - 1];
 
        vector<int> res;
        for(int i = 1;i <= n; ++ i)
        {pq.push(i);
            while(!pq.empty() and pq.top() < i - k + 1)pq.pop();
            if(i >= k)res.push_back(a[pq.top()]);
        }
 
        return res;
    }
};
退出移动版