题解 | 滑动窗口的最大值

滑动窗口的最大值

https://www.nowcoder.com/practice/1624bc35a45c42c0bc17d17fa0cba788

#include <climits>
#include <deque>
#include <vector>
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param num int整型vector 
     * @param size int整型 
     * @return int整型vector
     */
    vector<int> maxInWindows(vector<int>& num, int size) {
        // write code here
        vector<int> ans;
        if (size > num.size() || !size) return ans; // 特殊情况特殊处理
        deque<int> m; // 双端队列,存储可能的最大值
        for (int i = 0; i < num.size(); ++i) {
            while (!m.empty() && num[i] > m.back()) m.pop_back();
            m.push_back(num[i]);
            if (i >= size - 1) {
                ans.push_back(m.front());
                if (num[i - size + 1] == m.front()) m.pop_front();
            }
        }
        return ans;
    }
};

题干分析:

本题题目题目意思很清楚,即寻找定长滑动窗口中的最大值.根据题目意思,很容易得到时间复杂度为O(n * size)的暴力方法,即当每次构建成功一个窗口就遍历以便寻找最大值插入结果数组最后即可,但这显然达不到题目要求的O(n)时间复杂度,因此需要进行算法思路的优化.

优化方案1:

注: 该优化方案并不完美,只是提供一种思路,想直接看真正如何过本题可跳过此部分理解优化方案2即可.

首先,最容易想到的优化方案便是维护一个窗口当前最大值索引(也可以是最大值本身,但并不建议),当窗口发生滑动时,如果该索引尚未滑出窗口且新进入的值小于该索引指向的数组中的值便可直接使用此索引指向的数组中的值作为当前窗口的最大值插入结果数组最后.如果该索引未滑出窗口但新进入窗口的值大于该索引指向的数组中的值,更新此索引并将新的最大值插入结果数组最后.如果该索引滑出窗口,等窗口建立完毕,扫描整个窗口重新记录最大值索引并将最大值插入结果数组.

至于为什么保存的是索引而不建议保存最大值本身,主要是因为如果窗口中包含两个相同的最大值,只保存最大值本身会误判最大值已移出窗口,进而多一次遍历,虽然遍历之后还是会取得正确的最大值,但费了更多的时间,反之如果保存的是索引便能有效避免这种问题.

此类实现代码如下:

#include <climits>
#include <vector>
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param num int整型vector 
     * @param size int整型 
     * @return int整型vector
     */
    vector<int> maxInWindows(vector<int>& num, int size) {
        // write code here
        vector<int> ans;
        if (size > num.size() || !size) return ans; // 特殊情况特殊处理
        int m_idx = 0; // 最大值索引(默认数组第一个值为最大值)
        for (int i = 1; i < num.size(); ++i) {
            if (num[i] >= num[m_idx]) m_idx = i; // 新入窗口的值为最大值(注意当新进入窗口的值与最大值相等时也更新索引,避免无效遍历)
            if (i >= size - 1) { // 窗口已成型,记录当前窗口最大值后窗口左端开始滑动
                ans.push_back(num[m_idx]);
                if (i - size + 1 == m_idx) { // 窗口当前最大值移出窗口
					++m_idx; // 默认下一元素为当前窗口最大值
					for (int j = m_idx + 1; j <= i; ++j)
						if (num[j] >= num[m_idx]) m_idx = j; // 扫描取到当前窗口最大值索引
				}
            }
        }
        return ans;
    }
};

说明: 以上代码本人并未尝试提交过,很有可能超时.因为最坏的情况下,即当原数组为递减数组如[9,8,7,6,5,4,3,2,1]时,该算法和未优化前时间复杂度一样,均为O(n * size).

优化方案2:

我们从"优化方案1"得到的思路继续,已知方案1最大的问题是当保存的最大值信息(索引或者值)滑出窗口后需要重新扫描整个窗口获取新的最大值信息.那么有没有一种方案当当前窗口最大值滑出窗口后在O(1)的时间复杂度(因为题目要求总时间复杂度为O(n),遍历整个原数组复杂度为O(n),因此获取最大值信息并插入结果数组必须在常数时间复杂度内完成才符合题目要求)内获取滑动后窗口最大值信息呢?

从要求的时间复杂度出发,常数时间内就得获取下一最大值信息除非我们提前维护好可能的最大值信息,不然几乎做不到.问题便进一步转化为如何在窗口滑动后(具体来说是新元素进入窗口后)维护所有可能的最大值,以及选择适合的容器存放可能的最大值信息.

从"注"跳过来的可以从这里开始理解:

我们考虑一个可能的用例:[2,4,7,6,8,10,9,3,4,5,6,10,8,7], 5

我们能够将原数列(数组)分解为多个递增子列:{[2,4,7],[6,8],[10],[9],[3,4,5,6,10],[8],[7]}

现在我们模拟窗口的建立,滑动与可能最大值的保存过程:

首先2, 4, 7入窗口依次入窗口很明显的我们只需要保存7在可能最大值容器中即可,因为2,4总会比7早移出窗口,而2,4均小于7,无需保存.

然后6进入窗口,由于7会先于6滑出窗口,我们将6保存在容器中备用.

然后8进入窗口,我们对比最近进入容器的值6,由于8>6且8在6之后,6总会先于8出窗口,我们便能够将容器中的6去除,然后我们观察道,现在容器中的7也小于8,且7会先于8移出窗口,因此7也移出容器,此时容器为空,8直接进入容器.

此时,窗口初次建立,容器类保存了唯一的最大值8,将8写入结果数组中,然后剔除第一个进入窗口的值2(为下一窗口的建立做准备),由于2不是当前窗口最大值8,因此8不需要出容器.

然后10进入窗口,同8进入窗口时情况一致,8出容器,10进容器,窗口移动成功,写入结果10,同时剔除窗口末端的4,不影响最大值容器.

然后9进入窗口,同6进入窗口时情况一致,10不能出容器,同时9可能是新窗口的最大值,9入容器,窗口移动成功,写入结果10.

然后3进入窗口,同9进入窗口时情况一致,10和9都不出容器,3可能是未来窗口最大值,3入容器,窗口移动成功,写入结果10.