0

我正在尝试Leetcode 问题 239（最大滑动窗口）。
考虑两个实现，Sol1 和 Sol2。溶胶1：

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

溶胶2：

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        deque<int> dq;
        vector<int> ans;
        for (int i=0; i<nums.size(); i++) {
            if (!dq.empty() && dq.front() == i-k) dq.pop_front();
            while (!dq.empty() && nums[dq.back()] < nums[i]) dq.pop_back();
            dq.push_back(i);
            if (i>=k-1) ans.push_back(nums[dq.front()]);
        }
        return ans;
    }
};

Sol2 在以下方面与 Sol1 不同：

  • deque的back()方法已更改为front()，反之亦然。
  • deque的push_front()方法已更改为push_back()，反之亦然。
  • deque的pop_front()方法已更改为pop_back()，反之亦然。从逻辑上讲，这两种实现方式是相似的。

根据C++ 双端队列实现，

deques上常见操作的复杂度（效率）如下：

  • 随机访问 - 常数 O(1)
  • 在末尾或开头插入或删除元素 - 常量 O(1)
  • 插入或删除元素 - 线性 O(n)

但我观察到这些实现所消耗的时间和内存存在显着差异。我试图用几个编译器检查，差异仍然存在。

用于测试的结果和整个代码可以在这个gist中找到。为什么两种实现（Sol1 和 Sol2）之间存在差异？当我们使用不同的编译器时也有区别。我无法弄清楚这一点。任何帮助表示赞赏。

4

0 回答 0