在直方图中查找最大矩形区域中的酒吧索引

Question

我有一个直方图，我需要找到直方图下最大矩形内的酒吧索引。 找到直方图下的最大的矩形的方法是在这个环节

http://www.geeksforgeeks.org/largest-rectangle-under-histogram/

，并在网络上的多个环节解释。我无法检索输出矩形内的条的索引。 任何想法？ 谢谢

Answer 1

从已发布的链接：

对于HIST [TP]，“左指数”是以前的（以前以TP）项目在堆栈和“右指数”是“我'（当前指数）。

所以，你必须编辑getMaxArea（）方法来存储最大区域的左侧和右侧指标：

int getMaxArea(int hist[], int n) 
{ 
// .. 
int rindex=0; 
int lindex=0; 
while (i < n) 
{ 
//.. 
      if (max_area < area_with_top) 
      {max_area = area_with_top; 
      lindex=i-(max_area/hist[tp])+1; 
      rindex=i; 
      } 
//.. 
} 
while (s.empty() == false) 
{ 
//.. 
      if (max_area < area_with_top) 
      {max_area = area_with_top; 
      lindex=i-(max_area/hist[tp])+1; 
      rindex=i; 
      } 
//.. 
} 
//.. 
cout << "indexs: " << lindex << " " << rindex << "\n"; // u may pass them to main method, if needed 
return max_area; 
} 

我不是一个C++程序员，所以你可以优化我的尝试， 你可以在这里找到编辑的代码：ideone: online compiler