谜题：找到最大的矩形（最大矩形问题） [英] Puzzle: Find largest rectangle (maximal rectangle problem)

问题描述

什么是最有效的算法找出面积最大的矩形，将适合的空白？

What's the most efficient algorithm to find the rectangle with the largest area which will fit in the empty space?

比方说，屏幕看起来像这样（'＃'再presents填充区域）：

Let's say the screen looks like this ('#' represents filled area):

....................
..............######
##..................
.................###
.................###
#####...............
#####...............
#####...............

一个可能的解决方案是：

A probable solution is:

....................
..............######
##...++++++++++++...
.....++++++++++++###
.....++++++++++++###
#####++++++++++++...
#####++++++++++++...
#####++++++++++++...

通常我会喜欢找出一个解决方案。虽然这时候我想，避免浪费时间在我自己摸索周围，因为这有一个实际应用的一个项目我工作。有一个众所周知的解决方案？

Normally I'd enjoy figuring out a solution. Although this time I'd like to avoid wasting time fumbling around on my own since this has a practical use for a project I'm working on. Is there a well-known solution?

Shog9 写道：

是您输入数组（所隐含的其他反应），或在任意大小，位置矩形形式闭塞的列表（当与窗口位置处理的可能是一个窗口操作系统的情况）？

Is your input an array (as implied by the other responses), or a list of occlusions in the form of arbitrarily sized, positioned rectangles (as might be the case in a windowing system when dealing with window positions)?

是的，我有一个结构，它记录了一组放置在屏幕上的窗口中。我也有这使所有各边缘之间的区域的轨道，它们是否是空的或者填充网格，和它们的左或顶边的像素位置。我认为有一些修饰形式将采取这个属性的优势。你知道对否？

Yes, I have a structure which keeps track of a set of windows placed on the screen. I also have a grid which keeps track of all the areas between each edge, whether they are empty or filled, and the pixel position of their left or top edge. I think there is some modified form which would take advantage of this property. Do you know of any?

推荐答案

@lassevk

我发现引用的文章，从DDJ：的最大矩形问题

I found the referenced article, from DDJ: The Maximal Rectangle Problem

这篇关于谜题：找到最大的矩形（最大矩形问题）的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！