每日一题:滑动窗口最大值(LeetCode 239)

题目

给你一个整数数组 nums,有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
返回 滑动窗口中的最大值 。
输入:nums = [1,3,-1,-3,5,3,6,7], k = 3
输出:[3,3,5,5,6,7]

解析

此题使用单调队列解决,分享一段有趣的评论:

单调队列真是一种让人感到五味杂陈的数据结构,它的维护过程更是如此.....就拿此题来说,队头最大,往队尾方向单调......有机会站在队头的老大永远心狠手辣,当它从队尾杀进去的时候,如果它发现这里面没一个够自己打的,它会毫无人性地屠城,把原先队里的人头全部丢出去,转身建立起自己的政权,野心勃勃地准备开创一个新的王朝.....这时候,它的人格竟发生了一百八十度大反转,它变成了一位胸怀宽广的慈父!它热情地请那些新来的“小个子”们入住自己的王国......然而,这些小个子似乎天性都是一样的——嫉妒心强,倘若见到比自己还小的居然更早入住王国,它们会心狠手辣地找一个夜晚把它们通通干掉,好让自己享受更大的“蛋糕”;当然,遇到比自己强大的,它们也没辙,乖乖夹起尾巴做人。像这样的暗杀事件每天都在上演,虽然王国里日益笼罩上白色恐怖,但是好在没有后来者强大到足以干翻国王,江山还算能稳住。直到有一天,闯进来了一位真正厉害的角色,就像当年打江山的国王一样,手段狠辣,野心膨胀,于是又是大屠城......历史总是轮回的。

解答

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        //构建存储最大值的数组
        vector<int> res;

        if(nums.size() == 0 || k == 0)
        {
            return res;
        }
        //单调递减序列
        deque<int> dq;
        //一开始滑动窗口不包含K个元素,不是合格的滑动窗口
        for(int i = 0; i < k; i++)
        {
            while(!dq.empty() && dq.back() < nums[i])
            {
                dq.pop_back();
            }
            dq.push_back(nums[i]);
        }

        res.push_back(dq.front());

        for(int i = k; i < nums.size(); i++)
        {
            if(dq.front() == nums[i-k])
            {
                dq.pop_front();
            }

            while(!dq.empty() && dq.back() < nums[i])
            {
                dq.pop_back();
            }
            dq.push_back(nums[i]);

            res.push_back(dq.front());
        }

        return res;
    }
};
扫描关注程序区
THE END
分享
二维码
打赏
海报
每日一题:滑动窗口最大值(LeetCode 239)
题目 给你一个整数数组 nums,有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一……
<<上一篇
下一篇>>