[LeetCode] 0123. Mejor momento para comprar y vender acciones III

Explore diversas soluciones LeetCode en Python, C++, JavaScript, SQL y TypeScript. Ideal para preparación de entrevistas, aprendizaje y práctica de código en múltiples lenguajes de programación. Enlace de repositorio de Github

Tabla de contenido

Duro

Te dan una matriz precios dónde precios[i] es el precio de una determinada acción en el ^yo día.

Encuentra el máximo beneficio que puedes lograr. como máximo dos transacciones.

Nota: No puede realizar múltiples transacciones simultáneamente (es decir, debe vender las acciones antes de volver a comprarlas).

Ejemplo 1:

Aporte: precios = [3,3,5,0,0,3,1,4]
Producción: 6
Explicación: Compre el día 4 (precio = 0) y venda el día 6 (precio = 3), beneficio = 3-0 = 3. Luego compre el día 7 (precio = 1) y venda el día 8 (precio = 4), beneficio = 4-1 = 3.

Ejemplo 2:

Aporte: precios = [1,2,3,4,5]
Producción: 4
Explicación: Compre el día 1 (precio = 1) y venda el día 5 (precio = 5), ganancia = 5-1 = 4. Tenga en cuenta que no puede comprar el día 1, comprar el día 2 y venderlos más tarde, ya que está participando. múltiples transacciones al mismo tiempo Debes vender antes de volver a comprar.

Ejemplo 3:

Aporte: precios = [7,6,4,3,1]
Producción: 0
Explicación: En este caso, no se realiza ninguna transacción, es decir, beneficio máximo = 0.

Restricciones:

1 <= precios.longitud <= 10 ⁵
0 <= precios[i] <= 10 ⁵

Pitón

				
					Complejidad de tiempo de #: O(n) Complejidad de espacio de #: O(n) al escribir import Lista clase Solución(objeto): def maxProfit(self, precios: Lista[int]) -> int: si len(precios) <= 1 : retorno 0 leftMin = precios[0] rightMax = precios[-1] longitud = len(precios) leftProfits = [0] * longitud rightProfits = [0] * (longitud + 1) para l en el rango(1, longitud): leftProfits[l] = max(leftProfits[l - 1], precios[l] - leftMin) leftMin = min(leftMin, precios[l]) r = longitud - 1 - l rightProfits[r] = max(rightProfits[r + 1], rightMax - precios[r]) rightMax = max(rightMax, precios[r]) maxProfit = 0 print(leftProfits) print(rightProfits) para i en rango(0, longitud): maxProfit = max(maxProfit, leftProfits[ i] + rightProfits[i + 1]) devuelve precios maxProfit = [7, 1, 5, 3, 6, 4] # leftProfit = [0, 0, 4, 4, 5, 5] # rightProfit = [5, 5 , 3, 3, 0, 0, 0] print(Solución().maxProfit(precios))

Duro

Pitón

Artículos relacionados