使用双端队列的滑动窗口（运行时错误）

Question

在下面的程序中，我试图在长度为n的数组中找到k的窗口大小的最大值。供参考，该问题来自leetcode

例如，如果数组为[2 5 3 1 2]并且窗口大小为3，则我的窗口为[2 5 3]，[5 3 1]，[3 1 2]，相应的最大值为5， 5、3

我为此目的使用双端队列，但它给运行时带来了错误，我不认为正在发生任何指针无效，我找不到任何。请帮助我，我在这个问题上困扰了很长时间。

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        deque<int> d;
        for (int i = 0; i < k; ++i) {
            while (!d.empty() && d.front() < nums[i]) {
                d.pop_front();
            }
            d.push_front(nums[i]);
        }
        vector<int> ans;
        ans.push_back(d.back());

        int n = nums.size();
        for (int i = k; i < n; ++i) {
            while (1) {
                int elem = d.back();
                d.pop_back();
                if (elem == nums[i-k]) {
                    break;
                }
            }
            while (!d.empty() && d.front() < nums[i]) {
                d.pop_front();
            }
            d.push_front(nums[i]);
            ans.push_back(d.back());
        }
        return ans;
    }
};

显示的错误消息是：

第157行：字符16：运行时错误：类型为'int'的引用绑定到未对齐地址0xbebebebebebecc0ba，需要4字节对齐（stl_deque.h）0xbebebebebebecc0ba：注意：指针指向此处摘要：UndefinedBehaviorSanitizer：未定义行为/usr/bin/../lib/gcc/x86_64-linux-gnu/8/../../../../include/c++/8/bits/stl_deque.h ：162：16

Answer 1

观察代码的这一部分：

while (1) {
    int elem = d.back();
    d.pop_back();

    if (elem == nums[i-k]) {
        break;
    }
}

while循环没有脱离其第一次迭代。

您正在从双端队列中弹出元素，直到元素为空，因为elem不等于nums[i-k]。

将while (1)更改为：

while ( !d.empty() )

如果不为空，则可以从双端队列中获取并弹出一个元素。