c++ - 二维中一组点中以 X 轴为底的最大空矩形

Question

Original Problem: Problem 2

在一个高为500，宽为10^5的矩形空间中，给定N个点。

我们应该找出最大的子矩形，其底边在 x 轴上并且在其适当的内部不包含任何点(但可能在其边缘包含它们)。

我尝试了一个 O(width^2) 算法:

#include <iostream>
#include <algorithm>

const int nWidth = 100000;
const int nHeight = 500;

int main(){

  int *nMaxHeights = new int[nWidth];
  std::fill (nMaxHeights, nMaxHeights+nWidth, nHeight);

  int N;
  std::cin >> N;
  for (int x,y,iii=0; iii < N; iii++){
    std::cin >> x >> y;
    nMaxHeights[x] = std::min(y+1, nMaxHeights[x]);
  }

  int maxArea = 0;
  for (int jjj,iii=0; iii < nWidth; iii++){
    for (jjj=iii; jjj < nWidth; jjj++){
      if (nMaxHeights[jjj] < nMaxHeights[iii])
        break;
    }
    maxArea = std::max((jjj-iii+1)*nMaxHeights[iii],maxArea);
  }

  std::cout << maxArea;   

  return 0;
}

它有效，但显然会收到 TLE(超出执行时间限制)。

我怎样才能做得更好？

Answer 1

有趣的问题。感谢您指出这些。

我使用了一种算法，该算法将 O(N) 缩放为更大的 N(点数)和随机分布的点。其背后的想法:每个矩形将由一些点界定。

1. 如果一个 x 值有多个点，则只使用 y 值最低的点。
2. 首先检查极值x点；最右边和最左边，分别跨越一个矩形。限制。
3. 然后转到最右边的点并尝试构建一个包含它的矩形。有两种可能性:
   1. 这个点在水平边上:找到它的两个邻居，左边和右边，y 值较低，并将它们分别用作左边的点。右边缘。如果没有左/右邻居，则使用空格的末尾。
   2. 这个点在垂直边上:找到下一个左边的点，用空间的(y-)极限作为水平边。
4. 对于每个点，计算可能的矩形面积(上述两种可能性)，如果有任何大于当前最大面积，则更新最大面积。

这是 python 中的一些示例实现，http://pastebin.com/068ByYwh ，但我并不肯定，它不包含错误；-)