Given an array of integers heights representing the histogram's bar height where the width of each bar is 1, return the area of the largest rectangle in the histogram.

Example 1:

Input: heights = [2,1,5,6,2,3]
Output: 10
Explanation: The above is a histogram where width of each bar is 1.
The largest rectangle is shown in the red area, which has an area = 10 units.

Example 2:

Input: heights = [2,4]
Output: 4

1. A more intuitive solution:

Summary: Using 2 tables to memorize the left most index and right most index for current index i where height[i] can form a rectangle ( its height is less than or equal to all the rectangles between LeftMost[i] & RightMost[i].

For any bar i the maximum rectangle is of width r - l - 1 where r - is the last coordinate of the bar to the right with height h[r] >= h[i] and l - is the last coordinate of the bar to the left which height h[l] >= h[i]

So if for any i coordinate we know his utmost higher (or of the same height) neighbors to the right and to the left, we can easily find the largest rectangle:

int maxArea = 0;
for (int i = 0; i < height.length; i++) {
    maxArea = Math.max(maxArea, height[i] * (lessFromRight[i] - lessFromLeft[i] - 1));
}

The main trick is how to effectively calculate lessFromRight and lessFromLeft arrays. The trivial solution is to use O(n^2) solution and for each i element first find his left/right heighbour in the second inner loop just iterating back or forward:

for (int i = 1; i < height.length; i++) {
    int p = i - 1;
    while (p >= 0 && height[p] >= height[i]) {
        p--;
    }
    lessFromLeft[i] = p;
}

The only line change shifts this algorithm from O(n^2) to O(n) complexity: we don't need to rescan each item to the left - we can reuse results of previous calculations and "jump" through indices in quick manner:

while (p >= 0 && height[p] >= height[i]) {
      p = lessFromLeft[p];
}

Explanation:

Here's the intuition to understand p = lessFromLeft[p]; :

Consider the test caseindices.......... : 0 1 2 3 4 5 6 7 8 9 10 11heights.......... : 4 9 8 7 6 5 9 8 7 6 5 4.lessFromLeft :-1 0 0 0 0 0 5 5 5 5 . .

In this, when we reach 5 at index 10, we start searching for idx=9, i.e. p points at 6.6 > 5.Now, we want something which is smaller than 5, so it should definitely be smaller than 6. So 6 says to 5: