Найти индексы баров в наибольшей прямоугольной области в гистограмме

Question

У меня есть гистограмма, и мне нужно найти индексы баров внутри самого большого прямоугольника под гистограммой. способ найти самый большой прямоугольник под гистограммой объясняется в этой ссылке

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

и во многих других ссылок в Интернете. Я не могу получить индексы столбцов внутри прямоугольника вывода. Любые идеи? Спасибо

Answer 1

Из ссылки, которые вы публикуемая:

Для чужого [ф], то «левый индекс» является предыдущим (предшествующим ф) элементом в стеке и «правый индекс» есть «я '(текущий индекс).

Таким образом, вы должны изменить метод 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; 
} 

Im не C++ программиста, так что вы можете оптимизировать попробовать, You можно найти отредактированный код здесь: ideone: online compiler