问题在于具有N列的二维直方图，计算面积≥ K的矩形数量。列的宽度为 1，我知道第 i 列上的单位正方形的数量。
我提出了以下O(N²)算法：设h i为第 i列的高度。然后我可以执行以下操作：当我将i,j固定为矩形的底边时，我找到矩形h的最高可能高度并添加max(0, h - ceil(K/(j-i+1)) + 1)到答案中。
我听说有一个O(N log N)算法，我试图通过使用事实来推导它
∑<sup> N i=1 N ⁄<sub>i ~ N log N
但是，这就是我所拥有的一切，我无法取得进一步的进展。你能给出算法的提示吗？