数据分析题解

本题的主要核心是对单调栈和单调队列的理解和应用。

30 分的做法

由于 $1\le N\le10$ ，我们可以枚举每个区间（ $\mathcal{O}(N^2)$ ）然后从每个区间的最大值中求出来最小值。当然，我们还需要额外的 $\mathcal{O}(N)$ 时间来枚举每个区间长度求出所有答案。总复杂度 $\mathcal{O}(N^3)$ 。

60 分的做法

由于 $1\le N\le10^3$ ，如果我们继续用 $\mathcal{O}(N^2)$ 的时间求出区间的最大值，这个复杂度显然是难以承受的。我们来优化这个做法。

注意到现在问题转化成了给定区间长度 $k$ ，求出所有长度为 $k$ 子数组的最大值即可。这个问题是一个经典的滑动窗口最值问题，我们使用一个单调队列来解决。

考虑样例 1 且长度 $k=3$ 的前几步，如下图：

我们在队列中维护元素的下标（即右下角深绿色数字），维护策略如下：首先找到最原始序列的最大值推入队列中，然后我们在插入和删除新元素的时候统一处理队尾：如果当前元素大于队尾元素，说明队尾元素不可能在接下来的维护过程中成为最大值（当前元素会代替），所以我们持续弹出队尾元素，直到当前元素小于等于队尾元素或者队列为空。此时我们直接将当前元素插入到队尾，这个队列即从头到尾单调递减，保证队头元素就是当前窗口的最大值。

此时还有一个问题：如果这个值超过了当前区间怎么办？所以，我们还需要有队头的弹出操作，这也是我们维护数组下标的目的：当队头元素已经不在我们维护的窗口范围内时，直接弹出即可。由于整个队列都是单调的，这保证了我们弹出这个元素之后新的队头元素也能满足答案要求。

一种简单实现如下：

vector<int> findMaxK(vector<int>& numbers, int k) {
  deque<int> que;
  int n = numbers.size();

  vector<int> ans;

  for (int i = 0; i < n; i++) {
    while (!que.empty() && numbers[que.back()] < numbers[i]) {
      que.pop_back();
    }
    que.push_back(i);

    while (!que.empty() && que.front() == i - k) {
      que.pop_front();
    }

    if (i >= k - 1) ans.push_back(numbers[que.front()]);
  }

  return ans;
}

那么我们经过优化，对于给定长度只需要付出 $\mathcal{O}(N)$ 的时间就可以求出来所有滑动窗口的最大值，然后再 $\mathcal{O}(N)$ 找到其中的最小值就可以了。而枚举长度仍然需要 $\mathcal{O}(N)$ 的时间，总复杂度被我们优化到了 $\mathcal{O}(N^2)$ 。注意到每个元素只会进出队列一次，总空间复杂度 $\mathcal{O}(N)$ 。

100 分的做法

我们首先抛出来一个结论：如果某个数在 $k$ 长度的某个子区间内最大，那么对于长度 $k$ ，答案为这些数中的最小值。这个结论的证明其实很简单，我们考虑下面这个图：

可以看到，如果某个长度 $k$ 的所有窗口我们已经求出来了，那么我们移动长度同样为 $k$ 的窗口时，一定会和其中的一个或者多个窗口相交。而在这些情况下，这些相交窗口的最大值是大于等于我们求出来的这些值的，在之后求最小值的过程中一定不会选。所以，我们只需要求出来每个数所在的最大区间即可。

这个问题使用一个从栈顶到栈底递增的单调栈即可解决。我们考虑每个数最左边和最右边的第一个比自己大的数所在的位置，称为这个数的左边界和右边界。如果某个数进栈的时候比栈顶大，说明栈顶元素的右边界已经确定，直接弹出并更新右边界即可。更新完之后，栈顶的元素即比当前元素大的第一个元素，这就确定了当前元素的左边界，直接更新，最后插入当前元素即可。核心代码如下：

int n = numbers.size();
vector<int> left(n, -1), right(n, n);

stack<int> s;
for (int i = 0; i < n; i++) {
  while (!s.empty()) {
    auto t = s.top();
    if (numbers[t] <= numbers[i]) {
      right[t] = i;
      s.pop();
    } else {
      break;
    }
  }

  if (!s.empty()) {
    left[i] = s.top();
  }

  s.push(i);
}

此时 left[i] 和 right[i] 记录了元素 i 的左右边界，那么长度我们可以简单计算为 right[i] - left[i] - 1，直接遍历每个元素并更新答案即可。注意是遍历元素按长度更新答案，而不是枚举长度！

此时做完了吗？我们考虑上面图中的第一个例子，我们有 $k=4$ 的答案吗？没有。此时我们有另一个观察：对于长度为 $k$ 的答案，可以由 $k+1$ 直接转移过来。这个的观察其实十分显然：相当于每次我们枚举 $k+1$ 窗口的时候移除掉某个边界元素，这样会多产生一个值，而这个值并不会比 $k+1$ 的答案更小。所以，对于不存在的 $k$ 的答案，直接使用 $k+1$ 更新即可，否则我们不更新当前值。而另一个观察是， $k=N$ 的答案我们一定有（就是序列的最大值），所以我们直接从 $N-1$ 递减更新一下每一个长度的答案即可。

单调栈求出来左右边界需要 $\mathcal{O}(N)$ 的时间，我们更新答案需要两次遍历，也是 $\mathcal{O}(N)$ 的时间，总时间 $\mathcal{O}(N)$ 就可以搞定。注意到每个元素只会进出栈一次，总空间复杂度 $\mathcal{O}(N)$ 。

C++ 的参考代码如下：

class Solution {
public:
  /**
   * 找到所有长度子数组中最大值的最小值
   * @param numbers int整型vector
   * @return int整型vector
   */

  vector<int> getMinimums(vector<int>& numbers) {
    int n = numbers.size();
    vector<int> left(n, -1), right(n, n);
    vector<int> ans(n, numeric_limits<int>::max());

    stack<int> s;
    for (int i = 0; i < n; i++) {
      while (!s.empty()) {
        auto t = s.top();
        if (numbers[t] <= numbers[i]) {
          right[t] = i;
          s.pop();
        } else {
          break;
        }
      }

      if (!s.empty()) {
        left[i] = s.top();
      }

      s.push(i);
    }

    for (int i = 0; i < n; i++) {
      int sz = right[i] - left[i] - 1;
      ans[sz - 1] = min(ans[sz - 1], numbers[i]);
    }

    for (int i = n - 2; i >= 0; i--) {
      ans[i] = min(ans[i], ans[i + 1]);
    }

    return ans;
  }
};