Fácil–medio · casos límite

El segundo mayor

Encontrar el mayor ya sabes hacerlo. El segundo mayor es el mismo problema con una variable más, y una trampa: ¿qué pasa si todos los números son iguales?

En una fraseRecorre una sola vez guardando el mayor y el segundo mayor distinto; si todos los elementos son iguales no hay segundo mayor y la respuesta es la palabra none.

El problema

Entrada: La primera línea es un entero n (2 ≤ n ≤ 1000). La segunda línea contiene n enteros separados por espacios (−1000 ≤ a_i ≤ 1000).

Salida: El segundo valor distinto más grande. Si todos los números son iguales, imprime none.

Ejemplos:

Entrada	Salida
`5 3 9 2 9 7`	`7`
`4 1 1 1 1`	`none`
`3 -5 -3 -9`	`-5`

Toda la dificultad está en "distinto". Con 3 9 2 9 7 la respuesta es 7, no 9: el 9 aparece dos veces pero sigue siendo un solo valor.

Tu solución

main.cpp — tu solución

Entrada personalizada para «Ejecutar mi entrada»

La corrección corre en tu navegador contra pruebas ocultas. Un bucle infinito se corta a los 3 segundos — aun así, asegúrate de que todo bucle tenga salida. Tu código se guarda solo mientras escribes.

¿Atascado? Pistas

Pista 1 — Parte del máximo que ya conoces

Una variable big guarda el mayor visto hasta ahora. Añade otra, second. Cada vez que un número supera a big, el antiguo big desciende a second: esa línea es todo el truco.

Pista 2 — Dos ramas, no una

Si x > big, desplaza. Si no, si x es menor que big pero mayor que second, pasa a ser el nuevo second. Esa segunda rama hace inofensivos los duplicados: cuando x == big no se ejecuta ninguna, así que un máximo repetido nunca pisa al segundo.

Pista 3 — ¿Con qué valor empiezan las dos variables?

No 0. Las entradas pueden ser negativas, así que 0 parecería un "mayor" válido que nunca existió. Usa un valor por debajo de cualquier entrada legal, -1000000000, y al final comprueba si second sigue siendo ese centinela: si lo es, no había un segundo valor distinto.

Solución (¡inténtalo primero!)

#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;
    int big = -1000000000, second = -1000000000;
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        if (x > big) {
            second = big;
            big = x;
        } else if (x < big && x > second) {
            second = x;
        }
    }
    if (second == -1000000000) cout << "none" << endl;
    else cout << second << endl;
    return 0;
}

Fíjate en lo que no hiciste: no guardaste nada, no ordenaste nada. Un recorrido, dos variables, listo: O(n) de tiempo y O(1) de memoria. La misma forma de desplazar te da el tercer mayor, los dos menores o las dos mejores puntuaciones de un juego. Ahora lleva esa memoria O(1) a un problema donde el array sí hay que reordenarlo: Ordenamiento burbuja.

Análisis profundo

Por qué funciona

Un recorrido, dos variables y listo: sin array, sin ordenar. Esa forma de desplazar valores es el esqueleto de todos los problemas Top-K que encuentres.

El coste

O(n) de tiempo y O(1) de memoria. Ordenar primero y tomar el segundo es O(n log n) más una copia de los datos: extender toda la baraja para leer una carta.

Dónde falla

Empezar second en 0 imprime 0 con entradas todas negativas: una respuesta que no existe en los datos.
Escribir solo la rama x > big y olvidar x < big && x > second deja second clavado en el máximo anterior cuando hay valores repetidos.

Siguiente paso

Ahora deja que una regla se ejecute sola y mira dónde acaba: Pasos de Collatz.

Dos cosas para recordar

Dos variables y un descenso: cuando el nuevo rey sube al trono, el viejo pasa a segundo.
El centinela debe ser menor que cualquier entrada legal, o se hará pasar por respuesta.

🐞 Esta versión falla: ábrela y pruébala

second empieza en 0: con entradas negativas imprime 0

#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;
    int big = 0, second = 0;   // assumes the input is positive
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        if (x > big) {
            second = big;
            big = x;
        } else if (x < big && x > second) {
            second = x;
        }
    }
    cout << second << endl;
    return 0;
}