Maximisation de la somme des hauteurs de tours distinctes

Le problème consiste à attribuer une hauteur à chaque tour de manière à ce que toutes les hauteurs soient strictement distinctes, tout en respectant une limite maximale pour chaque tour, et en maximisant la somme totale des hauteurs.

Approche algorithmique

L'approche gloutonne optimale repose sur le tri des limites de hauteur. En parcourant le tableau de la plus grande limite vers la plus petite, on attribue à chaque tour la hauteur maximale possible. Cette hauteur est déterminée par le minimum entre sa limite initiale et la hauteur de la tour précédemment traitée moins un. Si à un moment donné la hauteur calculée devient nulle ou négative, la configuration est impossible et l'algorithme retourne une erreur.

Analyse de la complexité

• Complexité temporelle : O(N log N), dominée par l'opération de tri du tableau.
• Complexité spatiale : O(1) ou O(log N) selon l'implémentation du tri, car aucune structure de données supplémentaire significative n'est requise.

Implémentation

class TowerHeightOptimizer {
    public long computeMaxSum(int[] limits) {
        Arrays.sort(limits);
        long accumulatedHeight = limits[limits.length - 1];
        int currentMaxAllowed = limits[limits.length - 1];

        for (int idx = limits.length - 2; idx >= 0; idx--) {
            currentMaxAllowed = Math.min(limits[idx], currentMaxAllowed - 1);
            if (currentMaxAllowed <= 0) {
                return -1;
            }
            accumulatedHeight += currentMaxAllowed;
        }
        return accumulatedHeight;
    }
}

Rendre un tableau unique avec des incréments minimaux

L'objectif est de rendre tous les éléments d'un tableau uniques en effectuant le nombre minimum d'incréments sur les valeurs existantes.

Approche algorithmique

Après un tri ascendant du tableau, on parcourt les éléments en s'assurant que chaque valeur est strictement supérieure à la précédente. Si l'élément courant est inférieur ou égal à l'élément ajusté précédent, on l'incrémente jusqu'à atteindre valeur_précédente + 1. La différence entre la nouvelle valeur valide et l'ancienne est ajoutée au compteur total de mouvements. Cette méthode garantit que chaque élément trouve sa position unique la plus proche possible de sa valeur d'origine.

Analyse de la complexité

• Complexité temporelle : O(N log N), le goulot d'étranglement étant l'étape de tri.
• Complexité spatiale : O(1), l'ajustement se fait en place ou avec une variable d'état minimale.

Implémentation

class UniqueArrayAdjuster {
    public int calculateMinIncrements(int[] elements) {
        Arrays.sort(elements);
        int totalMoves = 0;
        int previousValue = elements[0];

        for (int idx = 1; idx < elements.length; idx++) {
            if (elements[idx] <= previousValue) {
                int nextValidValue = previousValue + 1;
                totalMoves += nextValidValue - elements[idx];
                previousValue = nextValidValue;
            } else {
                previousValue = elements[idx];
            }
        }
        return totalMoves;
    }
}

Maximiser l'élément après réduction et réarrangement

Le but est de maximiser l'élément le plus grand d'un tableau après l'avoir réarrangé, sous deux contraintes strictes : le premier élément doit être 1, et la différence absolue entre deux éléments adjacents ne doit pas dépasser 1.

Approche algorithmique

Le tri permet de traiter les éléments dans un ordre prévisible. On force le premier élément à 1 pour satisfiare la première contrainte. Pour les éléments suivants, on utilise une fonction minimum pour borner leur valeur à élément_précédent + 1. Cela garantit que la condition d'adjacence est respectée tout en conservant les valeurs aussi grandes que possible, maximisant ainsi le dernier élément du tableau.

Analyse de la complexité

• Complexité temporelle : O(N log N) due au tri initial.
• Complexité spatiale : O(1) pour les variables auxiliaires.

Implémentation

class ArrayRearranger {
    public int findMaxElement(int[] sequence) {
        Arrays.sort(sequence);
        sequence[0] = 1;

        for (int idx = 1; idx < sequence.length; idx++) {
            sequence[idx] = Math.min(sequence[idx], sequence[idx - 1] + 1);
        }
        return sequence[sequence.length - 1];
    }
}

Comptage maximal de points dans un carré avec étiquettes uniques

Ce problème demande de trouver le nombre maximum de points pouvant être contenus dans un carré centré à l'origine, tel que chaque point à l'intérieur du carré possède une étiquette de chaîne de caractères unique.

Approche algroithmique

Une recherche binaire est appliquée sur la taille du carré (définie par la distance maximale par rapport à l'origine sur les axes X et Y). Pour chaque taille candidate évaluée via le point médian, une fonction de validation vérifie si tous les points inclus ont des étiquettes uniques à l'aide d'un tableau de suivi booléen. Si des doublons sont détectés, la taille est réduite ; sinon, le nombre de points est enregistré et on tente d'agrandir le carré.

Analyse de la complexité

• Complexité temporelle : O(N log M), où N est le nombre de points et M est la coordonnée maximale absolue. La recherche binaire prend O(log M) et chaque validation prend O(N).
• Complexité spatiale : O(1) ou O(Σ) où Σ est la taille de l'alphabet (26 pour les lettres minuscules), pour le tableau de suivi des caractères.

Implémentation

class SquarePointCounter {
    public int maxPointsInSquare(int[][] coords, String labels) {
        int maxCoordinate = 0;
        for (int[] p : coords) {
            maxCoordinate = Math.max(maxCoordinate, Math.max(Math.abs(p[0]), Math.abs(p[1])));
        }

        int low = 0, high = maxCoordinate;
        int bestCount = 0;

        while (low <= high) {
            int mid = low + (high - low) / 2;
            int currentCount = validateAndCount(coords, labels, mid);
            
            if (currentCount != -1) {
                bestCount = Math.max(bestCount, currentCount);
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
        return bestCount;
    }

    private int validateAndCount(int[][] pts, String lbls, int size) {
        int seen = 0;
        boolean[] charTracker = new boolean[26];

        for (int i = 0; i < pts.length; i++) {
            int distX = Math.abs(pts[i][0]);
            int distY = Math.abs(pts[i][1]);

            if (distX <= size && distY <= size) {
                int charIdx = lbls.charAt(i) - 'a';
                if (charTracker[charIdx]) {
                    return -1; 
                }
                charTracker[charIdx] = true;
                seen++;
            }
        }
        return seen;
    }
}