1

In http://blog.csdn.net/arbuckle/archive/2006/05/06/710988.aspx, it was mentioned several methods to solve the Largest Rectangle in a Histogram problem. But I do not see how the first method, order-statistic tree, can be used to solve this problem. Could anyone please give a concrete example of this method, i.e. how the tree looks like for an example, let’s say, [7, 2, 1, 4, 5, 1, 3, 3]?

Qiang Li
  • 10,593
  • 21
  • 77
  • 148
  • I'd really love to answer your question, but I don't know what the "largest rectangle in a histogram" question is. Can you provide a link to the description of the inputs and expected output? Or give your own description. ? – templatetypedef Jan 07 '11 at 20:06
  • @templatetypedef: http://www.spoj.pl/problems/HISTOGRA/ is the link. BTW, the example i was trying to use is [7, 2, 1, 4, 5, 1, 3, 3]. Thanks! – Qiang Li Jan 08 '11 at 00:18
  • Is it possible for you to tell us what this largest rectangle is used for ? – Alexandre C. Jan 08 '11 at 00:28
  • @Alexandre C.: this isn't about the practicality of this specific problem. It is about how to cleverly design some algorithm to do this fast. Think of it as an intellectual challenge. Just like solving a very difficult planar geometry problem. :) – Qiang Li Jan 08 '11 at 01:24
  • @Qiang Li: okay. Is this question drawn from a specific programming challenge ? – Alexandre C. Jan 08 '11 at 10:22
  • Related: http://stackoverflow.com/questions/7245/puzzle-find-largest-rectangle-maximal-rectangle-problem – Alexandre C. Jan 08 '11 at 10:23

0 Answers0