基线位于x轴上的最大空矩形

Question

原始问题:问题2

在高度为500且宽度为10 ^ 5的矩形空间中,我们给出N个点.

我们应该找出最大的子矩形,其基部位于x轴上,并且不包含其正确内部的任何点(但可以在其边缘包含它们).

我尝试了一种O(宽度^ 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，但我不确定它不包含错误；-)