什么是两个直方图之间的最大积水量

Question

我最近遇到了这个问题：

您得到的高度为 n 个直方图，每个直方图的宽度为 1。您必须选择任意两个直方图，这样如果开始下雨并且所有其他直方图(您选择的两个除外(都被移除，那么在两个直方图之间收集的水将最大化。

Input: 9 3 2 5 9 7 8 1 4 6 Output: 25 在第三个和最后一个直方图之间。

这是捕获雨水问题的变体。

我尝试了两种解决方案，但两种解决方案的最坏情况复杂度均为 N^2。我们如何进一步优化。

• Sol1：每对的蛮力。

  int maxWaterCollected(vector<int> hist, int n) {
      int ans = 0;
      for (int i= 0; i < n; i++) {
          for (int j = i + 1; j < n; j++) {
              ans = max(ans, min(hist[i], hist[j]) * (j - i - 1));
          }
      }
      return ans;
  }
  

• Sol2：按高度递增顺序保留一系列直方图。对于每个直方图，在此序列中找到其最佳直方图。现在，如果所有直方图都按递增顺序排列，则此解决方案也变为 N^2。

  int maxWaterCollected(vector<int> hist, int n) {
      vector< pair<int, int> > increasingSeq(1, make_pair(hist[0], 0)); // initialised with 1st element.
      int ans = 0;
      for (int i = 1; i < n; i++) {
          // compute best result from current increasing sequence
          for (int j = 0; j < increasingSeq.size(); j++) {
              ans = max(ans, min(hist[i], increasingSeq[j].first) * (i - increasingSeq[j].second - 1));
          }
          // add this histogram to sequence
          if (hist[i] > increasingSeq.back().first) {
              increasingSeq.push_back(make_pair(hist[i], i));
          }
      }
      return ans;
  }
  

Answer 1

使用 2 个迭代器，一个来自 begin()，一个来自end() - 1。

• 直到 2 个迭代器相等：
• 将当前结果与最大值进行比较，并保持最大值
• 移动具有较小值的迭代器(开始 -> 结束或结束 ->开始(

复杂度：O(n)。

Answer 2

Jarod42 的想法是正确的，但从他的简短帖子中不清楚为什么他的算法(下面在 Python 中描述(是正确的：

def candidates(hist):
    l = 0
    r = len(hist) - 1
    while l < r:
        yield (r - l - 1) * min(hist[l], hist[r])
        if hist[l] <= hist[r]:
            l += 1
        else:
            r -= 1

def maxwater(hist):
    return max(candidates(hist))

正确性的证明是通过归纳法：最优解要么 (1( 属于到目前为止得到的候选者，要么 (2( 选择[l, r]内的直方图。基本情况很简单，因为所有直方图都在 [0, len(hist) - 1] 内。

归纳地，假设我们即将前进l或r。这些情况是对称的，所以让我们假设我们即将推进l。我们知道hist[l] <= hist[r]，所以值是(r - l - 1) * hist[l]。给定任何其他右端点r1 < r，该值为 (r1 - l - 1) * min(hist[l], hist[r1])，因为 r - l - 1 > r1 - l - 1 和 hist[l] >= min(hist[l], hist[r1]) 而较小。我们可以排除所有这些解决方案都是次优的，因此可以安全地推进l。