CSES - Advertisement

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 $\text{heights}[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.

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

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

using ll = long long;

int main() {
	int n;
	cin >> n;
	vector<ll> heights(n);
	for (ll &i : heights) { cin >> i; }

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.

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

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

using ll = long long;

int main() {
	int n;
	cin >> n;
	vector<ll> heights(n);
	for (ll &i : heights) { cin >> i; }

Alternatively, one can 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.

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

using ll = long long;

int main() {
	int n;
	cin >> n;
	vector<ll> heights(n);
	for (ll &i : heights) { cin >> i; }