LeetCode - Largest Rectangle in Histogram

Time Complexity: $\mathcal{O}(N)$.

Solution 1

The largest rectangle must have the same height as the shortest bar that it contains. For each $i$, consider the largest rectangle with height $H[i]$ such that bar $i$ is the shortest bar it contains. The answer is simply the largest of these $N$ rectangles.

Since the heights of these rectangles are fixed, we just want them to be as wide as possible. Notice how the rectangle of bar $i$ is bounded by the the closest shorter bars on each side of bar $i$ (or the ends of the histogram if these bars don't exist).

We can use a monotone stack twice to find the closest shorter bars on each side of each bar. See the stacks module for more details.

1#include <bits/stdc++.h>
2using namespace std;
3 
4using ll = long long;
5using ld = long double;
6using db = double; 
7using str = string; // yay python!
8
9using pi = pair<int,int>;
10using pl = pair<ll,ll>;

Solution 2

Actually, we only need to go through the heights in one direction. When we see (i, heights[i]), we process all rectangles with right end at i-1 and height greater than heights[i]. Note how we add -1 to the list of heights so we don't have to treat rectangles that end at the last height in heights as a special case.

1#include <bits/stdc++.h>
2using namespace std;
3 
4using ll = long long;
5using ld = long double;
6using db = double; 
7using str = string; // yay python!
8
9using pi = pair<int,int>;
10using pl = pair<ll,ll>;