stack.pop(); } right[i] = stack.isEmpty() ? n - 1 : stack.peek() - 1; } stack.push(i); } return right; }

Method 3 - Using One Monotonic Increasing Stack, O(n)

In the naive approach, there are some redundant iterations that we obviously could skip. For example: Given i=3 and j=2, the height is 1, and we already know that the area from i=2 to 0 is 3×1 because we previously traverse it when i=2.

Why Stack?

At each step we need the information of previously seen "candidate" bars - bars which give us hope. These are the bars of increasing heights. And since they'll need to be put in the order of their occurence, stack should come to your mind.

Lets take the example [2, 1, 5, 6, 2, 3]

Lets start by adding a bar of height 0 as starting point to the stack. This has no inherent meaning, and is just done to make the solution more elegant.

largest-rectangle-in-histogram-eg1.excalidraw

The first bar we see is the bar at position 0 of height

Related Tags