Skip to Content
CTRL K

Mike and Feet

Análisis oficial (C++) 

Explicación

Empecemos considerando al oso ii. Si este oso es el más bajo de un grupo, entonces ese grupo solo se extiende hasta que encontramos otro oso más bajo que el oso ii.

Esto significa que para cada oso queremos hallar:

  • El oso más cercano a la izquierda que sea más bajo
  • El oso más cercano a la derecha que sea más bajo

Digamos que están en los índices L[i]\texttt{L}[i] y R[i]\texttt{R}[i], respectivamente. Sabemos que el oso ii es el más bajo de cualquier grupo que quede entre ellos, así que el grupo más grande posible donde el oso ii es el más bajo tiene tamaño R[i]−L[i]−1\texttt{R}[i] - \texttt{L}[i] - 1.

Ahora, supongamos que el oso ii puede determinar la fuerza de un grupo de tamaño ss. Entonces su altura es potencialmente la fuerza máxima entre todos los grupos de tamaño ss. Sin embargo, aunque guardamos el grupo más grande en el que puede estar el oso ii, cualquier grupo más pequeño anidado en este grupo mayor también tendría al oso ii como el más bajo. Así, si un oso sirve para un grupo de tamaño ss, también sirve para todos los tamaños de grupo menores. Para tener esto en cuenta, podemos iterar del tamaño de grupo más grande al más pequeño, donde strengths[i]=max(strengths[i], strengths[i+1])\texttt{strengths}[i] = \texttt{max}(\texttt{strengths}[i],~\texttt{strengths}[i+1]).

Para hallar los osos más bajos más cercanos L[i]\texttt{L}[i] y R[i]\texttt{R}[i], usamos una pila monótona. Mientras recorremos los osos, mientras la altura del oso en la cima de la pila sea mayor o igual que la altura del oso actual ii, desapilamos el oso de la cima. Tras desapilar todos esos osos, el que queda en la cima es el oso más bajo más cercano, así que guardamos su índice en L[i]\texttt{L}[i] o R[i]\texttt{R}[i]. Luego apilamos el oso ii.

Implementación

Complejidad temporal: O(N)\mathcal{O}(N)

N = int(input())
heights = list(map(int, input().split()))
L = [-1] * N  # oso más cercano a la izquierda más bajo que el oso i
R = [N] * N  # oso más cercano a la derecha más bajo que el oso i
 
stack_left = []
for i in range(N):
	while stack_left and heights[stack_left[-1]] >= heights[i]:
		stack_left.pop()
	if stack_left:
		L[i] = stack_left[-1]
	else:
		L[i] = -1
	stack_left.append(i)
 
stack_right = []
for i in range(N - 1, -1, -1):
	while stack_right and heights[stack_right[-1]] >= heights[i]:
		stack_right.pop()
	if stack_right:
		R[i] = stack_right[-1]
	else:
		R[i] = N
	stack_right.append(i)
 
strengths = [0] * N
for i in range(N):
	# grupo más largo donde el oso i es el más bajo
	length = R[i] - L[i] - 2  # -2 por indexación desde cero
	if heights[i] > strengths[length]:
		strengths[length] = heights[i]
 
# tener en cuenta grupos más pequeños dentro de los más grandes
for k in range(N - 2, -1, -1):
	strengths[k] = max(strengths[k], strengths[k + 1])
 
print(" ".join(map(str, strengths)))
Fundamentos