滑动窗口的最大值

一、题目

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

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

leetcode：https://leetcode.cn/problems/sliding-window-maximum/

二、思路

这个题目 O(k*N) 的时间复杂度是达不到要求的，需要得到一个 O(N) 的时间复杂度。那么我们的思考过程，我们要拿到每次滑动窗口的最大值，重点是要在滑动的时候就求出这个窗口内的最大值，而且我们是可以做到的。那么我们选择什么数据结构来存储这个最大值呢，这个数据结构需要可以两端都可以进出，选择双端队列再合适不过了

假设我们遍历到 arr[i] 这个位置，对于插入队列：如果队列为空，直接插入队尾；否则我们拿 queue.back() 值进行比较。队列插入的是下标，而非值。

如果 arr[i] < queue.back() 值，插入队列尾部。我们的队列从队头到队尾依次是从大到小。保存 arr[i] 是因为 arr[i] 可能是接下来其他滑动窗口的最大值，因此需要保存。
如果 arr[i] >= queue.back() 值，这个时候从队列尾开始出元素，将那些比 arr[i] 小的元素全部出队列。为什么这么做呢？这个晚到的 arr[i] 是个大值，当前的滑动窗口，队列中比他小的元素没有竞争性了；接下来的滑动窗口中，队列中比他小的元素更没有竞争性了。所以循环依次将队列中比 arr[i] 小的元素出队列，因为没有什么用了。

也就是我们保证队列中从队头到队尾是从大到小。方便我们取到滑动窗口的最大值。另外一个，通俗来说，

如果来了较小值，哪还有可能是接下来滑动窗口的最大值，因为队列中的大元素在滑动窗口过去之后需要出队列。
如果来了较大值，那队列中比他小（小于等于）的元素得全部出队列，因为来了一个比他晚到、而且比他大的元素，没有竞争性了

什么时候需要从队列中弹出元素呢？就是队列中元素过期了，滑动窗口再也用不到他的时候，直接从队头弹出。

三、code

#include <vector>
#include <deque>
#include <iostream>

using namespace std;

void print_queue(std::deque<int> qu) {
    std::deque<int> help_qu;
    while (!qu.empty()) {
        help_qu.push_back(qu.back());
        std::cout << qu.back() << " ";
        qu.pop_back();
    }
    std::cout << std::endl;
    while (!help_qu.empty()) {
        qu.push_front(help_qu.front());
        help_qu.pop_front();
    }
}

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        std::vector<int> res;
        for (size_t i = 0; i < nums.size(); ++i) {
            if (!queue_.empty() && nums[i] < nums[queue_.back()]) {
                queue_.push_back(i);
            } else {
                for (; !queue_.empty() && nums[i] >= nums[queue_.back()]; ) {
                    queue_.pop_back();
                }
                // 直到队列为空了，或者 nums[i] < nums[queue_.back() 了，尾插 nums[i]
                queue_.push_back(i);
            }
            print_queue(queue_);
            // 插完之后，在每个阶段，我们都需要清理队列中过期的元素，从队头出。nums[i-k] 是当前滑动窗口第一个过期元素。
            // 注意，一定要在取滑动窗口最大值之前，让过期元素出队列，否则可能取到过期的元素
            if (queue_.front() == i-k) {
                queue_.pop_front();
            }
            // 当一个滑动窗口中所有元素都遍历了，就可以获取最大值了。
            // 也就是说，从第 k-1 次遍历，我们就得到了滑动窗口，后面都应该收集拿最大值
            if (queue_.back() >= k-1) {
                res.emplace_back(nums[queue_.front()]);
            }
        }
        return res;
    }

private:
    std::deque<int> queue_;
};

int main() {
    Solution s;
    std::vector<int> vec{1,3,-1,-3,5,3,6,7};
    // std::vector<int> vec{1, -1};
    int k = 3;
    auto res = s.maxSlidingWindow(vec, k);
    for (const auto& x : res) {
        std::cout << x << " ";
    }
    std::cout << std::endl;
}

时间复杂度：O(n)
空间复杂度：O(k)