find largest rectangle in histogram on python (stack method)
Вследствие отстутствия в рунете внятного разъяснения данной темы - "подсчёт самого большого прямоугольника в гистограмме", при помощи подробного разъяснения полученного из данного видео: https://www.youtube.com/watch?v=VNbkzsnllsU разберём и реализуем его на языке python(файл в папке find rectangle in histogram(RU).py).
для примера используем смешанный комплексный ряд [2,1,4,5,1,3,3],чтобы включить основные особенности расчета.

На рис.1: P(position)-индекс для столбца, нумеруем начиная с нуля, С(count bars)-количество клеток в стобце
Наш изначальный стек в нулевом состоянии:
| P | C |
| 0 | 0 |

1.P=0; C=2
заносим данные в стек, если значение С в стеке меньше чем С1, т.е. в данном случае заносим значения P и С:
| P | C |
| 0 | 2 |

формула для подсчета количества прямоугольников:
size=C(index+1-P), где index- номер столбца, используемого в данный момент
2.P=1; C=1, т.к. С=1, меньше значения С в стеке(С=2), С=1 замещает С=2, а P-остаётся без изменений
| P | C |
| 0 | 1 |


3.P=2; C=4, т.к. С=4 больше С=1(из стека), то добавляем в стек P и С. Подсчет size,во время наполнения стека, можно не производить
| P | C |
| 0 | 1 |
| 2 | 4 |

4.P=3; C=5, аналогично шагу 3, наполняем стек
| P | C |
| 0 | 1 |
| 2 | 4 |
| 3 | 5 |

5.P=4; C=1, здесь С=1 меньше С=5(верхушка стека), и мы должны приравнять бы, поставить С=1 на место С=5, ОДНАКО - в стеке уже есть С=1(выше), поэтому необходимо выполнить сброс стека до значения С=1, но до этого подсчитать size со всеми значениями стека, со значением index = 3(позиция P, перед текущей P=4)
| P | C |
| 0 | 1 |
| 2 | 4 |
| 3 | 5 |


6.P=5; C=3, состояние нашего стека после шага 5 -
| P | C |
| 0 | 1 |

т.к. С=3 больше С=1, следовательно добавляем значения P и С в стек
| P | C |
| 0 | 1 |
| 5 | 3 |

Аналогично шагу 3,подсчет size,во время наполнения стека, можно не производить
7.P=6; C=3, аналогично шагу 6, добавляем значения P и C в стек
| P | C |
| 0 | 1 |
| 5 | 3 |
| 6 | 3 |

8. Все стобцы пройдены, теперь рабоатем с тем, что в стеке:
index=6,т.к. он последний

Последнее значение, равное 7 - это значение нижнего ряда по ширине
Теперь из всех значений size, выбираем большее, и это size=8