LeetCode – Rectángulo más grande en histograma (Java)

Dado n números enteros no negativos que representan la altura de la barra del histograma donde el ancho de cada barra es 1, encuentre el área del rectángulo más grande en el histograma.

Arriba hay un histograma donde el ancho de cada barra es 1, dada la altura = [2,1,5,6,2,3].

El rectángulo más grande se muestra en el área sombreada, que tiene un área = 10 unidades.

Por ejemplo, dada la altura = [2,1,5,6,2,3], devuelve 10.

Análisis

Si una barra está bloqueada por una barra inferior, entonces la barra más alta ya no es necesario considerarla. Solo necesitamos hacer un seguimiento de las barras que no están bloqueadas. A medida que iteramos sobre las barras, cada vez que una barra bloquea una barra anterior, calculamos cuánta área puede soportar la barra anterior.

La clave para resolver este problema es mantener una pila para almacenar los índices de las barras. La pila solo conserva las barras crecientes.

Solución Java

public int largestRectangleArea(int[] height) {
	if (height == null || height.length == 0) {
		return 0;
	}
 
	Stack<Integer> stack = new Stack<Integer>();
 
	int max = 0;
	int i = 0;
 
	while (i < height.length) {
		//push index to stack when the current height is larger than the previous one
		if (stack.isEmpty() || height[i] >= height[stack.peek()]) {
			stack.push(i);
			i++;
		} else {
		//calculate max value when the current height is less than the previous one
			int p = stack.pop();
			int h = height[p];
			int w = stack.isEmpty() ? i : i - stack.peek() - 1;
			max = Math.max(h * w, max);
		}
 
	}
 
	while (!stack.isEmpty()) {
		int p = stack.pop();
		int h = height[p];
		int w = stack.isEmpty() ? i : i - stack.peek() - 1;
		max = Math.max(h * w, max);
	}
 
	return max;
}