Skip to Content
CTRL K

Advertisement

Solución 1

El rectángulo más grande debe tener la misma altura que la barra más corta que contiene. Para cada ii, consideramos el rectángulo más grande de altura heights[i]\text{heights}[i] tal que la barra ii es la barra más corta que contiene. La respuesta es simplemente el más grande de estos nn rectángulos.

Como las alturas de estos rectángulos están fijas, solo queremos que sean lo más anchos posible. Observemos que el rectángulo de la barra ii está acotado por las barras más cortas más cercanas a cada lado de la barra ii (o los extremos del histograma si esas barras no existen).

Podemos usar una pila monótona dos veces para hallar las barras más cortas más cercanas a cada lado de cada barra. Ver el módulo de pilas para más detalles.

Implementación

Complejidad temporal: O(N)\mathcal O(N).

#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; }
 
	stack<int> mono_stack;
	vector<ll> area(n, 0);
 
	// de izquierda a derecha
	for (int i = 0; i < n; i++) {
		while (!mono_stack.empty() && heights[mono_stack.top()] >= heights[i]) {
			mono_stack.pop();
		}
		int width = i - (mono_stack.empty() ? -1 : mono_stack.top());
		area[i] += width * heights[i];
		mono_stack.push(i);
	}
	while (!mono_stack.empty()) { mono_stack.pop(); }
 
	// de derecha a izquierda
	for (int i = n - 1; i >= 0; i--) {
		while (!mono_stack.empty() && heights[mono_stack.top()] >= heights[i]) {
			mono_stack.pop();
		}
		int width = (mono_stack.empty() ? n : mono_stack.top()) - i;
		area[i] += (width - 1) * heights[i];
		mono_stack.push(i);
	}
 
	cout << *max_element(area.begin(), area.end()) << endl;
}
n = int(input())
heights = list(map(int, input().split()))
 
mono_stack = []
area = [0] * n
 
# de izquierda a derecha
for i in range(n):
	while mono_stack and heights[mono_stack[-1]] >= heights[i]:
		mono_stack.pop()
	width = i - (-1 if not mono_stack else mono_stack[-1])
	area[i] += width * heights[i]
	mono_stack.append(i)
 
while mono_stack:
	mono_stack.pop()
 
# de derecha a izquierda
for i in range(n - 1, -1, -1):
	while mono_stack and heights[mono_stack[-1]] >= heights[i]:
		mono_stack.pop()
	width = (n if not mono_stack else mono_stack[-1]) - i
	area[i] += (width - 1) * heights[i]
	mono_stack.append(i)
 
print(max(area))

Solución 2

En realidad, solo hay que recorrer las alturas en una dirección. Cuando vemos (i, heights[i]), procesamos todos los rectángulos con extremo derecho en i-1 y altura mayor que heights[i]. Nótese cómo procesamos los rectángulos que terminan en la última altura vaciando la pila.

Implementación

Complejidad temporal: O(N)\mathcal O(N).

#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; }
 
	ll ans = 0;
	stack<pair<ll, ll>> mono_stack;
	for (int i = 0; i < n; i++) {
		int start = i;
		while (!mono_stack.empty() && heights[i] < mono_stack.top().second) {
			pair<ll, ll> cur = mono_stack.top();
			mono_stack.pop();
			start = cur.first;
			ans = max(ans, (i - cur.first) * cur.second);
		}
		mono_stack.push({start, heights[i]});
	}
 
	// terminar los rectángulos restantes
	while (!mono_stack.empty()) {
		pair<ll, ll> cur = mono_stack.top();
		mono_stack.pop();
		ans = max(ans, (n - cur.first) * cur.second);
	}
 
	cout << ans << endl;
}
n = int(input())
heights = list(map(int, input().split()))
 
ans = 0
mono_stack = []
 
for i in range(n):
	start = i
	while mono_stack and heights[i] < mono_stack[-1][1]:
		curr = mono_stack[-1]
		mono_stack.pop()
		start = curr[0]
		ans = max(ans, (i - curr[0]) * curr[1])
 
	mono_stack.append([start, heights[i]])
 
# terminar los rectángulos restantes
while mono_stack:
	curr = mono_stack[-1]
	mono_stack.pop()
	ans = max(ans, (n - curr[0]) * curr[1])
 
print(ans)

Como alternativa, se puede agregar -1 a la lista de heights para no tener que tratar los rectángulos que terminan en la última altura de heights como un caso especial.

Implementación

#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; }
	heights.push_back(-1);
 
	stack<ll> mono_stack;
	mono_stack.push(-1);
 
	ll ans = 0;
	for (int i = 0; i <= n; i++) {
		while (mono_stack.top() != -1 && heights[mono_stack.top()] >= heights[i]) {
			int x = mono_stack.top();
			mono_stack.pop();
			// la altura mínima es heights[x]
			ll new_area = (i - 1 - mono_stack.top()) * heights[x];
			if (ans < new_area) { ans = new_area; }
		}
		mono_stack.push(i);
	}
 
	cout << ans << endl;
}
n = int(input())
heights = list(map(int, input().split()))
heights.append(-1)
 
mono_stack = [-1]
ans = 0
 
for i in range(n + 1):
	while mono_stack[-1] != -1 and heights[mono_stack[-1]] >= heights[i]:
		x = mono_stack[-1]
		mono_stack.pop()
		# la altura mínima es heights[x]
		new_area = (i - 1 - mono_stack[-1]) * heights[x]
		ans = max(ans, new_area)
 
	mono_stack.append(i)
 
print(ans)
Fundamentos