问在网上参加了一次实习技术面试，我错过了什么？

EN

您可以在O(nlogn)中为子集使用一个min堆和一个最大堆来完成这一任务。遍历数组时，从堆中移除第一个元素并添加新元素。

解决长输入序列的顺序子序列问题的最简单方法是使用(单端)队列，至少在概念上是这样。(在输入是向量而不是流的情况下，实际上不需要存储队列，但如果队列是显式的，则算法通常更清晰。)

在这种情况下，解决方案需要在队列的最大值和最小值之间找到最大的差异。如果我们想要一个O(1)解决方案，我们需要一个队列，其中操作push_back、pop_front、min和max都是O(1)。

首先要注意的是，如果我们正在寻找一个具有该属性的堆栈(其中pop_front被pop_back替换)，那么解决方案非常简单:每当我们推送一个新值时，我们就计算出新的min和max，并将它们与新值一起推送。当我们弹出一个值时，我们也会弹出相关的min和max，并且保持在堆栈顶部的min和max也是正确的。

我们如何将其转换为队列？答案是，我们需要使用堆栈实现队列。或者更准确地说，使用两个堆栈。这就是所谓的“银行家队列”，它使用两个(功能性)堆栈提供一个摊销的O(1) (functional)队列。

这是一个简单的技巧:一个堆栈--前面的堆栈--用来推，另一个堆栈--后面的堆栈--用于弹出。队列的前面保持在前面的堆栈中，而队列的后面在后端堆栈上保持相反的顺序，因此后端堆栈的顶部是队列中的第一个元素。这很好，直到后台堆栈为空，我们需要弹出第一个元素。在这一点上，我们只需一次弹出前面堆栈中的元素，然后将每个元素推到后面堆栈上。一旦我们这样做了，前面的堆栈是空的，后面堆栈的顶部是前面堆栈中的最后一个元素，这是队列的第一个元素，正如我们所希望的那样。

很明显，上面的实现是摊销的O(1)，因为每个元素都被推到每个堆栈上一次(并且从每个堆栈弹出一次)。当然，每个操作实际上并不是O(1)：每隔一段时间，pop_front就会花费相当长的时间。但平均水平总是正确的。(另一方面，推总是O(1)。)

因此，我们可以用两个最小-最大的堆栈组成一个最小-最大的队列，并利用它来解决最大范围问题。

有了这个大纲，很容易找到一些优化。首先，我们可以将两个堆栈存储在同一个数组中，如果我们向后存储堆栈并与前堆栈相邻，那么我们只需要跟踪两个堆栈之间边界的位置，而弹出前堆栈并将该值推到后端堆栈的操作包括简单地移动边界指针。(对于min堆栈，我们需要计算mins和maxes。)这将导致一个简单的循环缓冲区实现，这是一个常见的队列解决方案。

此外，在移动窗口的情况下，队列的大小是已知的，因此我们不必处理动态调整大小。而且，在输入是向量的情况下，我们不需要实际将元素推到前面的堆栈上，因为元素位于输入的已知位置，并且不需要前面堆栈中的堆栈min/max值。

我希望所有这些都足以解释这个C++实现：

#include <algorithm>
#include <vector>

using std::min;
using std::max;

struct minmax { int min; int max; };

int maxrange(const std::vector<int>& v, int n) {
  int sz = v.size();
  n = min(n, sz);
  if (n <= 1) return 0;
  // The stack only needs n - 2 elements. So this could be adjusted.
  minmax* stack = new minmax[n];
  int loback, hiback, lofront, hifront;
  int maxrange = 0;
  for (int s = n - 1, m = 0; s < sz; ++s, --m) {
    if (m == 0) {
      lofront = hifront = v[s];
      loback = hiback = v[s - 1];
      for (int i = 2; i < n; ++i) {
        stack[i - 2] = minmax{loback, hiback};
        loback = min(loback, v[s - i]);
        hiback = max(hiback, v[s - i]);
      }
      m = n - 1;
    } else {
      lofront = min(lofront, v[s]);
      hifront = max(hifront, v[s]);
      loback = stack[m-1].min;
      hiback = stack[m-1].max;
    }
    maxrange = max(maxrange, max(hifront, hiback) - min(lofront, loback));
  }
  delete[] stack;
  return maxrange;
}

输入：

int inp[]={...},n=...;

1. 为输入创建int索引数组 N=sizeof(inp)/sizeof(inp)；
2. 索引排序inp[N]在ix[N]升序中(保持inp[N]不变)

- so for any `i={0,1,2,...,N-2}` is `(inp[ix[i]]<=inp[ix[i+1]])==true`
- this can be done in `O(N*log(N))`

​

1. 现在，从1<n<=N开始的大小int i0=0,1,2,...N-n的任何子集都是这样完成的： int i1=i0+n-1；//子集的有效索引为: i0<=i<=i1；int min=0，max=0；for (i= 0;i< N;i++) if ((ixi>=i0)&(ixi<=i1)){ min=inp[ixi]；max=；} for (i=N1；i>=0；i-) if (ixi>=i0)&&i0；(ixi<=i1){ max=inp[ixi]；} int diff=max-min；
2. 周期项目3贯穿所有地点

- and find the max diff ...

​

备注

• 这对于较大的n来说更快，对于较小的n则更慢。
• 因此，最好的方法是使用您的方法，这是根据n个大小调整的。