Plus grand rectangle dans un histogramme
Utilisez une pile monotone pour suivre les frontières gauches et calculer, en un seul parcours, l’aire maximale d’un rectangle contenu dans un histogramme.
Plus grand rectangle dans un histogramme est une leçon Coding Interview Prep gratuite sur CoddyKit. Ceci est la leçon 2 sur 4. Tu peux lire la leçon complète ci-dessous gratuitement — puis la pratiquer en direct dans le navigateur avec un éditeur de code intégré et un tuteur IA 24/7. Elle fait partie du parcours d'apprentissage Coding Interview Prep, et ta progression se synchronise sur le web et l'application CoddyKit. Le cours Coding Interview Prep comprend 4 leçons au total.
Problème : plus grand rectangle dans un histogramme
Le problème du plus grand rectangle dans un histogramme (LeetCode 84) fournit un tableau d’entiers non négatifs représentant les hauteurs de barres d’un histogramme, chaque barre ayant une largeur de 1. Trouvez l’aire du plus grand rectangle pouvant être formé dans l’histogramme. Le rectangle doit couvrir des barres contiguës et sa hauteur est limitée par la barre la plus courte qu’il couvre.
Une approche par force brute consiste, pour chaque paire (i, j), à calculer la hauteur minimale dans [i, j] et à la multiplier par (j - i + 1). Cela donne une complexité en O(n³), ou en O(n²) avec des minimums pré-calculés — ce qui est trop lent. La solution utilisant une pile monotone s’exécute en O(n).
# Example: heights = [2, 1, 5, 6, 2, 3]
# Rectangles:
# width=1, height=6 at index 3 => area=6
# width=2, height=5 at indices 2-3 => area=10 (maximum!)
# width=6, height=1 across all => area=6
# width=3, height=2 at indices 2-4 => area=6
heights = [2, 1, 5, 6, 2, 3]
print('Heights:', heights)
print('Expected max area: 10 (bars of height 5 and 6, width 2)')
# Brute force for small inputs:
def brute_force(heights):
n = len(heights)
max_area = 0
for i in range(n):
min_h = heights[i]
for j in range(i, n):
min_h = min(min_h, heights[j])
max_area = max(max_area, min_h * (j - i + 1))
return max_area
print('Brute force answer:', brute_force(heights)) # 10Idée clé : qu’est-ce qui limite le rectangle de chaque barre ?
Pour chaque barre i de hauteur h, le plus grand rectangle dont elle peut constituer le minimum s’étend vers la gauche jusqu’à la première barre plus courte que h, et vers la droite jusqu’à la première barre plus courte que h. La largeur est right_boundary - left_boundary - 1 et l’aire est h × width.
Cette reformulation du problème consiste à trouver, pour chaque barre, son élément inférieur précédent et son élément inférieur suivant. C’est exactement ce que calcule une pile croissante monotone. Au moment où nous dépilons la barre i (parce qu’une barre plus courte a été trouvée), la barre actuelle est son élément inférieur suivant et le sommet de la pile après le dépilement est son élément inférieur précédent.
heights = [2, 1, 5, 6, 2, 3]
n = len(heights)
# Find PSE and NSE for each bar
pse = [-1] * n # index of previous smaller element
nse = [n] * n # index of next smaller element (default: beyond array)
# PSE
stack = []
for i in range(n):
while stack and heights[stack[-1]] >= heights[i]:
stack.pop()
pse[i] = stack[-1] if stack else -1
stack.append(i)
# NSE
stack = []
for i in range(n - 1, -1, -1):
while stack and heights[stack[-1]] >= heights[i]:
stack.pop()
nse[i] = stack[-1] if stack else n
stack.append(i)
max_area = 0
for i in range(n):
width = nse[i] - pse[i] - 1
area = heights[i] * width
print(f'Bar {i} (h={heights[i]}): PSE={pse[i]}, NSE={nse[i]}, width={width}, area={area}')
max_area = max(max_area, area)
print('Max area:', max_area)Solution en un seul passage avec une pile monotone
L’approche en deux passages précédente fonctionne, mais peut être regroupée en un seul passage. Parcourez les barres de gauche à droite avec une pile croissante monotone. Lorsque la barre i est plus courte que le sommet de la pile, dépilez le sommet — la hauteur de la barre dépilée est la hauteur d’un rectangle, sa limite droite est i et sa limite gauche est le nouveau sommet de la pile + 1.
Une astuce courante consiste à utiliser append pour ajouter une sentinelle 0 à la fin du tableau des hauteurs. Cela garantit que toutes les barres sont dépilées à la fin, même si aucune barre plus courte n’apparaît naturellement. Sans la sentinelle, vous devez effectuer une phase de nettoyage après la boucle pour les éléments restants de la pile.
def largest_rectangle(heights):
stack = [] # monotonic increasing: indices of bars
max_area = 0
heights = heights + [0] # sentinel: forces all bars to be popped
for i, h in enumerate(heights):
while stack and heights[stack[-1]] > h:
height = heights[stack.pop()] # height of the rectangle
width = i if not stack else i - stack[-1] - 1 # left boundary
max_area = max(max_area, height * width)
stack.append(i)
return max_area
print(largest_rectangle([2, 1, 5, 6, 2, 3])) # 10
print(largest_rectangle([2, 4])) # 4
print(largest_rectangle([1, 1])) # 2
print(largest_rectangle([0, 9])) # 9
print(largest_rectangle([6, 7, 5, 2, 4, 5, 9, 3])) # 16Suivre l’algorithme en un seul passage
Suivons [2, 1, 5, 6, 2, 3, 0] (avec une sentinelle) étape par étape :
- i=0, h=2 : empiler 0. Pile : [0]
- i=1, h=1 : pop 0 (h=2, largeur=1, aire=2). Pile vide, empiler 1. Pile : [1]
- i=2, h=5 : 5>1, empiler 2. Pile : [1,2]
- i=3, h=6 : 6>5, empiler 3. Pile : [1,2,3]
- i=4, h=2 : pop 3 (h=6,largeur=4-2-1=1,aire=6), pop 2 (h=5,largeur=4-1-1=2,aire=10★), 2>1, arrêt. Empiler 4. Pile : [1,4]
- i=5, h=3 : 3>2, empiler 5. Pile : [1,4,5]
- i=6, h=0, sentinelle : faire pop de toute la pile en calculant les aires…
def largest_rectangle_trace(heights):
stack = []
max_area = 0
hs = heights + [0]
for i, h in enumerate(hs):
while stack and hs[stack[-1]] > h:
top = stack.pop()
w = i if not stack else i - stack[-1] - 1
area = hs[top] * w
print(f' Pop bar {top} (h={hs[top]}): width={w}, area={area}', end='')
if area > max_area:
max_area = area
print(' *** NEW MAX ***', end='')
print()
print(f'i={i} h={h}: push {i}, stack={[hs[s] for s in stack + [i]]}')
stack.append(i)
print(f'Max area: {max_area}')
return max_area
largest_rectangle_trace([2, 1, 5, 6, 2, 3])Calcul de la largeur : pourquoi i - stack[-1] - 1 ?
Lorsque nous faisons pop de la barre j de la pile, nous savons que la limite droite de son rectangle est i (la première barre plus courte que j à droite). La limite gauche est la barre située immédiatement sous j dans la pile après le dépilement — appelons-la k. La largeur est donc i - k - 1 (les barres de k+1 à i-1 incluses).
Si la pile est vide après le dépilement, le rectangle de j s’étend jusqu’au bord gauche (indice 0). La largeur vaut simplement i (les indices 0 à i-1, dont les barres ont toutes une hauteur au moins égale à heights[j]). Il s’agit du cas particulier width = i if not stack else i - stack[-1] - 1.
# Illustrating left/right boundary logic
heights = [1, 3, 5, 2]
# After processing with stack:
# When we pop bar 2 (h=5) at i=3 (h=2):
# stack after pop = [0, 1] => left boundary = 1+1=2, right=3-1=2 => width=1
# When we pop bar 1 (h=3) at i=3 (h=2):
# stack after pop = [0] => left boundary = 0+1=1, right=3-1=2 => width=2
# etc.
def compute_boundaries(heights):
hs = heights + [0]
stack = []
for i, h in enumerate(hs):
while stack and hs[stack[-1]] > h:
top = stack.pop()
if stack:
left = stack[-1] + 1
width = i - stack[-1] - 1
else:
left = 0
width = i
print(f'Bar {top} (h={hs[top]}): extends from {left} to {i-1}, width={width}')
stack.append(i)
compute_boundaries([2, 1, 5, 6, 2, 3])Rectangle maximal dans une matrice binaire
Rectangle maximal (LeetCode 85) étend le problème de l’histogramme à une matrice binaire en deux dimensions. Pour chaque ligne, calculez la hauteur des 1 consécutifs au-dessus de chaque cellule. Cela crée un histogramme pour cette ligne. Appliquez l’algorithme du plus grand rectangle dans un histogramme à l’histogramme de chaque ligne. Le maximum global parmi toutes les lignes est la réponse.
Cela réduit un problème en deux dimensions à n problèmes d’histogramme en une dimension répétés. La complexité temporelle est O(m × n) pour une matrice de m lignes et n colonnes : un parcours de l’histogramme par ligne, chaque parcours s’effectuant en O(n).
def maximal_rectangle(matrix):
if not matrix or not matrix[0]:
return 0
n = len(matrix[0])
heights = [0] * n
max_area = 0
def hist_max_area(h):
stack, area = [], 0
for i, hh in enumerate(h + [0]):
while stack and h[stack[-1]] > hh:
top = stack.pop()
w = i if not stack else i - stack[-1] - 1
area = max(area, h[top] * w)
stack.append(i)
return area
for row in matrix:
for j in range(n):
heights[j] = heights[j] + 1 if row[j] == '1' else 0
max_area = max(max_area, hist_max_area(heights[:]))
return max_area
matrix = [['1','0','1','0','0'],
['1','0','1','1','1'],
['1','1','1','1','1'],
['1','0','0','1','0']]
print(maximal_rectangle(matrix)) # 6Cas limites des problèmes d’histogramme
Cas limites importants à gérer :
- Toutes les hauteurs sont identiques : le tableau entier forme un seul rectangle ; résultat = n × hauteur
- Hauteurs monotones croissantes : aucun dépilement ne se produit avant la sentinelle ; l’aire de la dernière barre est maximale
- Une seule barre : résultat = hauteur[0]
- Barres de hauteur 0 : elles jouent le rôle de sentinelles naturelles et divisent l’histogramme en segments indépendants
La sentinelle (append 0) à la fin gère le cas des hauteurs monotones croissantes en forçant le dépilement de toutes les barres restantes à la fin. Sans elle, vous devez ajouter une boucle de nettoyage distincte après l’itération principale.
def largest_rectangle(heights):
stack = []
max_area = 0
heights = heights + [0]
for i, h in enumerate(heights):
while stack and heights[stack[-1]] > h:
top = stack.pop()
w = i if not stack else i - stack[-1] - 1
max_area = max(max_area, heights[top] * w)
stack.append(i)
return max_area
# Edge cases
print(largest_rectangle([5, 5, 5, 5])) # 20 (all same)
print(largest_rectangle([1, 2, 3, 4, 5])) # 9 (increasing: 3*3)
print(largest_rectangle([5, 4, 3, 2, 1])) # 9 (decreasing: 3*3)
print(largest_rectangle([5])) # 5 (single bar)
print(largest_rectangle([0, 0, 0])) # 0 (all zero)
print(largest_rectangle([3, 0, 3])) # 3 (zero splits)Autre solution : diviser pour régner
Le problème de l’histogramme peut également être résolu en divisant pour régner : séparez le tableau au niveau de la barre de hauteur minimale, résolvez récursivement chaque moitié et comparez avec le rectangle couvrant toute la largeur à la hauteur minimale. Cela donne une complexité moyenne en O(n log n), mais une complexité en O(n²) dans le pire des cas pour des entrées triées.
L’approche par pile monotone est strictement meilleure, avec une complexité en O(n) dans le pire des cas. Toutefois, comprendre l’approche consistant à diviser pour régner approfondit l’intuition du problème et explique pourquoi la barre de hauteur minimale d’un segment est toujours le facteur limitant des rectangles couvrant toute sa largeur.
def largest_rectangle_dc(heights, lo=0, hi=None):
if hi is None:
hi = len(heights) - 1
if lo > hi:
return 0
# Find the index of the minimum height in [lo, hi]
min_idx = lo
for i in range(lo, hi + 1):
if heights[i] < heights[min_idx]:
min_idx = i
# Three options:
# 1. Max rect entirely in left half
# 2. Max rect entirely in right half
# 3. Max rect spanning entire [lo, hi] with height = min
full_width_area = heights[min_idx] * (hi - lo + 1)
left_area = largest_rectangle_dc(heights, lo, min_idx - 1)
right_area = largest_rectangle_dc(heights, min_idx + 1, hi)
return max(full_width_area, left_area, right_area)
print(largest_rectangle_dc([2, 1, 5, 6, 2, 3])) # 10Motif d’histogramme : nombre de sous-tableaux
Un problème connexe utilisant la même technique de pile consiste à compter le nombre de sous-tableaux d’un histogramme dont l’élément minimal est égal à une certaine cible. Pour y répondre, calculez l’élément inférieur précédent et l’élément inférieur suivant de chaque barre, puis utilisez la formule (i - pse[i]) × (nse[i] - i), qui compte les sous-histogrammes dans lesquels la barre i est minimale.
Cette technique du « nombre à gauche × nombre à droite » apparaît dans plusieurs problèmes de LeetCode : somme des minimums des sous-tableaux (907), comptage des sous-chaînes dont tous les caractères sont uniques et problèmes fondés sur la technique des contributions. La pile monotone calcule l’élément inférieur précédent et l’élément inférieur suivant en O(n), ce qui permet de calculer la contribution de chaque élément en O(1).
def sum_of_subarray_minimums(arr):
n = len(arr)
pse = [-1] * n # previous strictly smaller element
nse = [n] * n # next smaller or equal element
stack = []
for i in range(n):
while stack and arr[stack[-1]] >= arr[i]:
stack.pop()
pse[i] = stack[-1] if stack else -1
stack.append(i)
stack = []
for i in range(n - 1, -1, -1):
while stack and arr[stack[-1]] > arr[i]:
stack.pop()
nse[i] = stack[-1] if stack else n
stack.append(i)
MOD = 10**9 + 7
total = 0
for i in range(n):
left_count = i - pse[i] # subarrays where i is leftmost min
right_count = nse[i] - i # subarrays where i is the min
total += arr[i] * left_count * right_count
return total % MOD
print(sum_of_subarray_minimums([3, 1, 2, 4])) # 17
print(sum_of_subarray_minimums([11, 81, 94, 43, 3])) # 444Conseils pratiques pour les entretiens
Lorsque vous rencontrez un problème d'histogramme en entretien, suivez cette liste de vérification :
- Clarifiez : les hauteurs peuvent-elles être nulles ? Quelle est la sortie — une aire, des indices ou un nombre ?
- Commencez par la force brute et indiquez une complexité en O(n²) ou O(n³)
- Mentionnez que la contribution de chaque barre dépend de son extension vers la gauche et vers la droite jusqu'à la barre plus courte la plus proche
- Présentez PSE/NSE → pile monotone → solution en O(n)
- Gérez l'astuce de la sentinelle (append 0) pour simplifier le code
- Suivez un petit exemple au tableau blanc
Une question complémentaire fréquente consiste à passer au cas 2D (rectangle maximal). Montrez que vous pouvez le réduire à n problèmes d'histogramme, chacun en O(n), pour un total en O(m×n).
# Final clean solution for interview
def largest_rectangle_in_histogram(heights):
stack = []
max_area = 0
for i, h in enumerate(heights + [0]): # sentinel forces final pops
while stack and heights[stack[-1]] > h:
height = heights[stack.pop()]
width = i if not stack else i - stack[-1] - 1
max_area = max(max_area, height * width)
stack.append(i)
return max_area
# Verify all test cases from earlier
test_cases = [
([2, 1, 5, 6, 2, 3], 10),
([6, 7, 5, 2, 4, 5, 9, 3], 16),
([1], 1),
([2, 0, 2], 2),
([], 0),
]
for heights, expected in test_cases:
if not heights:
result = 0
else:
result = largest_rectangle_in_histogram(heights)
status = 'PASS' if result == expected else 'FAIL'
print(f'{status}: {heights} => {result} (expected {expected})')Somme des plages de sous-tableaux et variantes similaires
La technique PSE/NSE se généralise à plusieurs problèmes de LeetCode. Somme des plages de sous-tableaux (2104) demande la somme de (maximum − minimum) pour tous les sous-tableaux. Cela équivaut à (somme des maximums des sous-tableaux) moins (somme des minimums des sous-tableaux), chacun étant calculé avec une pile monotone en O(n). Nombre de personnes visibles dans une file (1944) utilise une pile décroissante où chaque pop comptabilise une personne visible. La reconnaissance de cette famille de problèmes vient de l'observation de la question « pour chaque élément, jusqu'où peut-il dominer ? » — la réponse est toujours PSE/NSE avec une pile monotone.
def sum_subarray_ranges(nums):
n = len(nums)
# Sum of subarray max - sum of subarray min
def contrib(arr, is_max):
# Count contribution of each element as max (or min)
n = len(arr)
left = [0]*n; right = [0]*n
stack = []
for i in range(n):
while stack and (arr[stack[-1]] < arr[i] if is_max else arr[stack[-1]] > arr[i]):
stack.pop()
left[i] = i - (stack[-1] if stack else -1)
stack.append(i)
stack = []
for i in range(n-1, -1, -1):
while stack and (arr[stack[-1]] <= arr[i] if is_max else arr[stack[-1]] >= arr[i]):
stack.pop()
right[i] = (stack[-1] if stack else n) - i
stack.append(i)
return sum(arr[i] * left[i] * right[i] for i in range(n))
return contrib(nums, True) - contrib(nums, False)
print(sum_subarray_ranges([1, 2, 3])) # 4
print(sum_subarray_ranges([1, 3, 3])) # 4
print(sum_subarray_ranges([4, -2, -3, 4, 1])) # 59Vérification rapide
Évaluez votre compréhension des concepts de Structures de données & algorithmes — préparation aux entretiens de programmation de cette leçon.
Récapitulatif de la leçon
Dans cette leçon, vous avez appris : pour chaque barre, le plus grand rectangle qui la contient a pour limites la barre plus courte la plus proche de chaque côté (PSE et NSE), une pile monotone croissante calcule toutes les limites PSE/NSE en un seul parcours O(n), en trouvant les deux lorsque les barres sont retirées, et l'ajout d'une sentinelle 0 garantit que toutes les barres sont retirées de la pile, ce qui réduit le code à une seule boucle. Ensuite, vous allez appliquer la file monotone à double extrémité pour résoudre le problème du maximum d'une fenêtre glissante en O(n).
Questions Fréquemment Posées
La leçon « Plus grand rectangle dans un histogramme » est-elle gratuite ?
Oui — le texte complet de « Plus grand rectangle dans un histogramme » est gratuit à lire ici sur le web. Pour la pratiquer de manière interactive (un éditeur de code intégré et un tuteur IA 24/7) et déverrouiller le reste du cours Coding Interview Prep, passe à CoddyKit PRO. Le cours Coding Interview Prep comprend 4 leçons au total.
Qu'est-ce que j'apprendrai dans « Plus grand rectangle dans un histogramme » ?
Utilisez une pile monotone pour suivre les frontières gauches et calculer, en un seul parcours, l’aire maximale d’un rectangle contenu dans un histogramme. Tu pratiques Coding Interview Prep avec du code pratique que tu exécutes directement dans le navigateur, et un tuteur IA 24/7 répond à tes questions au fur et à mesure que tu avances dans la leçon.
Dois-je avoir de l'expérience pour commencer Coding Interview Prep ?
Aucune expérience préalable n'est requise. Coding Interview Prep sur CoddyKit est structuré pour les débutants jusqu'aux apprenants avancés, donc tu peux commencer ici ou depuis le début et avancer à ton rythme. Ceci est la leçon 2 sur 4.
Combien de temps prend la leçon « Plus grand rectangle dans un histogramme » ?
La plupart des leçons CoddyKit prennent environ 5–10 minutes. Chacune est courte et interactive, tu progresses régulièrement et tu repiques exactement où tu t'es arrêté sur le web et l'app.
Peux-tu écrire et exécuter du code dans cette leçon Coding Interview Prep ?
Oui. Chaque leçon Coding Interview Prep inclut un éditeur de code intégré, tu écris et exécutes du vrai code directement dans ton navigateur et tu reçois des retours IA instantanés — aucune configuration locale requise.
Toutes les leçons de ce cours
- Pile monotone : croissante ou décroissante
- Plus grand rectangle dans un histogramme
- Maximum dans une fenêtre glissante avec une deque monotone
- Accumulation d’eau de pluie : pile et deux pointeurs