239. 滑动窗口最大值(Sliding Window Maximum)

题目描述:

给定一个数组 nums,有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。

返回滑动窗口中的最大值。

 

进阶:

你能在线性时间复杂度内解决此题吗?

 

示例:

输入: nums = [1,3,-1,-3,5,3,6,7], 和 k = 3
输出: [3,3,5,5,6,7]

解题思路:

  这道题用单调队列可以快速解决。假如滑动窗口内有i < j,并且nums[i] <= nums[j],那么其实永远取不到nums[i]。理解这一点以后就可以得知,滑动窗口内只用保存i < j,并且nums[i] > nums[j]的点,这就是单调队列。

  其次如果直接在滑动窗口内保存值的话,很难得知当前值是否是应该被pop的那个。所以滑动窗口应该保存下标,如果下标等于应该pop的元素的下标,那么就pop它。

  代码如下:

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        deque<int> window;
        for (int i = 0; i < k; ++i) {
            if (window.empty())
                window.push_back(i);
            else {
                while (!window.empty() && nums[window.back()] <= nums[i])
                    window.pop_back();
                window.push_back(i);
            }
        }

        vector<int> res;
        for (int i = k; i < nums.size(); ++i) {
            res.push_back(nums[window.front()]);
            if (window.front() == i - k)
                window.pop_front();
            while (!window.empty() && nums[window.back()] <= nums[i])
                window.pop_back();
            window.push_back(i);
        }
        res.push_back(nums[window.front()]);
        return res;
    }
};

 

239. 滑动窗口最大值(Sliding Window Maximum)

上一篇:什么是API接口测试?用Restbird、Postman工具助力接口自动化测试


下一篇:win10上玩转docker emulator