darwinrlo
commented
4 years ago Consider a bar i. Bar i + 1 is shorter than bar i. For any rectangle including bar i and with a right bar at i + 1 or later, the height of the rectangle will not exceed the height of bar i + 1.
Compute the following rectangle.
- Bar i is the rightmost bar.
- The rectangle is as tall as bar i.
- The rectangle extends as far left as possible while maintaining its height. (The bar at )
The area of the largest rectangle between i and j
Say we are given bars i and j such that bar i appears earlier in the histogram than bar j (that is, i < j). Consider the largest rectangle starting at i and ending at j. The height of the rectangle is the height of the shortest bar between bars i and j, possibly bars i or j. The width of the rectangle is j - i + 1. The area of the rectangle is the product of the width and the height just calculated.