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.

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
	int largestRectangleArea(vector<int>& heights) {
		int n = heights.size();
		if (!n) return 0;
		stack<int> stck;
		vector<int> area(n, 0);

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 process the rectangles that end at the last height by emptying the stack.

#include <bits/stdc++.h>
using namespace std;
#define pi pair<int, int>
#define f first
#define s second
class Solution {
public:
	int largestRectangleArea(vector<int>& heights) {
		int N = heights.size();
		int maxa = 0;

Alternative implementation: 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.

#include <bits/stdc++.h>
using namespace std;
 
using ll = long long;
using ld = long double;
using db = double; 
using str = string; // yay python!

using pi = pair<int,int>;
using pl = pair<ll,ll>;