在直方图中找到最大矩形区域中的条形索引

Question

我有一个直方图，我需要找到直方图下最大矩形内的条形索引。在这个link

中解释了找到直方图下最大矩形的方法

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

以及网络上的许多其他 link。我无法检索输出矩形内的条形索引。有任何想法吗？谢谢

Answer 1

来自您发布的link：

For hist[tp], the ‘left index’ is previous (previous to tp) item in stack and ‘right index’ is ‘i’ (current index).

所以你必须编辑 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

在直方图中找到最大矩形区域中的条形索引

Find the bars indexes in the largest Rectangular Area in a Histogram

c#

algorithm

image-processing

visual-studio-2012