LeetCode 239.滑动窗口最大值

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

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

思路:

使用一个deque表示窗口,每进入一个元素,“删除”比新元素小的,这样可以保证每次移动窗口,最大值都是窗口最前面的那个元素。

示例:

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

2020061510105220

代码:

vector<int> maxSlidingWindow(vector<int>& nums, int k)
{
    deque<int> window;  // 存储数据的下标
    vector<int> res;

    for (int i = 0; i < nums.size(); ++ i)
    {   // nums[i] 即将进入窗口
        if (i >= k && window[0] <= i - k)   // 以下标来判断窗口是否"满"
            window.pop_front();                         // 老元素离开窗口

        while (!window.empty()
            && nums[window[window.size() - 1]] <= nums[i])
            // 踢出比 nums[i] 小的,想想为什么从后向前?

        window.pop_back();

        window.emplace_back(i);         // 新元素进入窗口

        if (i >= k - 1)             // 跳过前 k 次
            res.emplace_back(nums[window[0]]);  // 最大值在窗口最前面
    }

    return res;
}
喜欢()
评论 (0)