使用双端队列滑动 window（运行时错误）

Question

在下面的程序中，我试图在长度为 n 的数组中找到 k 的 window 大小的最大值。作为参考，问题来自LeetCode.

例如，如果数组是 [2 5 3 1 2] 并且 window 大小是 3，那么我有 windows 为 [2 5 3]，[5 3 1]， [3 1 2] 对应的最大值是 5, 5, 3.

我为此目的使用了 std::deque，但它给出了运行时错误，我认为没有任何 指针失效 发生，我找不到任何。请帮助我，我被困了很长时间。

这是我的代码：

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;
    }
};

显示的错误消息是这样的：

Line 157: Char 16: runtime error: reference binding to misaligned address 0xbebebebebebec0ba for type 'int', which requires 4 byte alignment (stl_deque.h)
0xbebebebebebec0ba: note: pointer points here
<memory cannot be printed>
SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior /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();         // get element
    d.pop_back();                // pop element

    if (elem == nums[i-k]) {     // compare element
        break;                   // and break on success
    }                            // What happens on failure???
}                                // Inifinite loop and UB!

while 循环没有退出。

在每次迭代中，您都会从双端队列中访问并弹出一个元素，直到它为空，因为 elem 不等于 nums[i-k]。

将while (1)更改为：

while ( !d.empty() )

因为只有当双端队列不为空时，您才能从双端队列中获取和弹出元素！

并且，在空双端队列上调用 back() 和 pop_back() 是 Undefined Behavior:

来自 std::deque::back() 的文档：

Calling back on an empty container causes undefined behavior.

std::deque::pop_back()也是如此：

Calling pop_back on an empty container is undefined.

Answer 2

抱歉，我忍不住想做一个替代实现。

因此，我试图更接近滑动的隐喻 window – 即在现有向量上滑动开始和结束索引以确定子范围的最大值。

我仍然记得存在一种接受初始化列表的 std::max() 风格。（我的初衷就是想用它。）

然而，当我在谷歌上搜索（回忆细节并获得手边的链接）时，我偶然发现了更好的东西（也由 <algorithm> 提供）：

std::max_element

Finds the greatest element in the range [first, last).

所以，我制作了一个 MCVE 来查看 std::max_element() 的效果：

#include <iostream>
#include <algorithm>
#include <vector>

std::vector<int> maxSlidingWindow(
  const std::vector<int> &nums, // the sample data
  int k) // the length of sliding window
{
  if (k <= 0) return { }; // no maxima for insufficient range
  if ((size_t)k > nums.size()) k = nums.size(); // Ehem... window too large
  std::vector<int> ans;
  //ans.reserve(num.size() - k); // allocate final size at once (for more speed)
  for (size_t i = k; i <= nums.size(); ++i) {
    ans.push_back(
      *std::max_element(nums.begin() + i - k, nums.begin() + i));
  }
  return ans;
}      

std::ostream& operator<<(std::ostream &out, const std::vector<int> &vec)
{
  const char *sep = "";
  for (int value : vec) {
    out << sep << value;
    sep = " ";
  }
  return out;
}

int main()
{
  std::vector<int> sample = { 2, 5, 3, 1, 2 };
  std::cout << "Input: " << sample << '\n';
  std::cout << "Output: " << maxSlidingWindow(sample, 3) << '\n';
}

输出：

Input: 2 5 3 1 2
Output: 5 5 3

Live Demo on coliru

使用双端队列滑动 window（运行时错误）

Sliding window using deque (runtime error)

c++

data-structures

runtime-error

deque