Maximiser la zone rectangular sous Histogramme

Les réponses ci-dessus ont donné la meilleure solution O (n) en code, cependant, leurs explications sont assez difficiles à comprendre. L’algorithme O (n) utilisant une stack m’a semblé magique au début, mais pour le moment, cela a tout son sens. OK, laisse-moi t’expliquer.

Première observation:

Pour trouver le rectangle maximal, si pour chaque barre x , nous connaissons la première barre plus petite de chaque côté, disons l et r , nous sums certains que la height[x] * (r - l - 1) est la meilleure peut obtenir en utilisant la hauteur de la barre x . Dans la figure ci-dessous, 1 et 2 sont les premiers plus petits de 5.

OK, supposons que nous pouvons faire cela en temps O (1) pour chaque barre, alors nous pouvons résoudre ce problème dans O (n)! en balayant chaque barre.

Ensuite, la question se pose: pour chaque barre, pouvons-nous vraiment trouver la première barre plus petite à sa gauche et à sa droite dans le temps O (1)? Cela semble impossible non? … C’est possible, en utilisant une stack croissante.

Pourquoi utiliser une stack croissante peut-il garder une trace du premier plus petit à sa gauche et à sa droite?

Peut-être qu’en vous disant qu’une stack de plus en plus importante peut faire l’affaire, le travail n’est pas du tout convaincant, alors je vais vous en parler.

Tout d’abord, pour que la stack continue à augmenter, nous avons besoin d’une opération:

 while x < stack.top(): stack.pop() stack.push(x) 

Ensuite, vous pouvez vérifier que dans la stack croissante (comme illustré ci-dessous), pour la stack[x] , la stack[x-1] est la première plus petite à gauche, alors un nouvel élément pouvant sortir la stack[x] est le premier plus petit à sa droite.

Vous ne pouvez toujours pas croire que la stack [x-1] est la première plus petite à gauche de la stack [x]?

Je vais le prouver par contradiction.

Tout d'abord, la stack[x-1] < stack[x] est sûre. Mais supposons que la stack[x-1] n'est pas la première plus petite à gauche de la stack[x] .

Alors, où sont les premiers petits fs ?

 If fs < stack[x-1]: stack[x-1] will be popped out by fs, else fs >= stack[x-1]: fs shall be pushed into stack, Either case will result fs lie between stack[x-1] and stack[x], which is contradicting to the fact that there is no item between stack[x-1] and stack[x]. 

Par conséquent, la stack [x-1] doit être la première plus petite.

Résumé:

L'augmentation de la stack peut garder la trace du premier plus petit à gauche et à droite pour chaque élément. En utilisant cette propriété, le rectangle maximal dans l'histogramme peut être résolu en utilisant une stack dans O (n).

Toutes nos félicitations! C'est vraiment un problème difficile, je suis content que mes explications prosaïques ne vous aient pas empêché de finir. Ci-joint ma solution prouvée comme récompense 🙂

 def largestRectangleArea(A): ans = 0 A = [-1] + A A.append(-1) n = len(A) stack = [0] # store index for i in range(n): while A[i] < A[stack[-1]]: h = A[stack.pop()] area = h*(i-stack[-1]-1) ans = max(ans, area) stack.append(i) return ans 

Il y a trois façons de résoudre ce problème en plus de l’approche par force brute. Je vais tous les écrire. Les codes Java ont passé des tests sur un site de juge en ligne appelé leetcode: http://www.leetcode.com/onlinejudge#question_84 . donc je suis confiant que les codes sont corrects.

Solution 1: programmation dynamic + n * n masortingce en cache

time: O (n ^ 2), espace: O (n ^ 2)

Idée de base: utilisez la masortingce n * n dp [i] [j] pour mettre en cache la hauteur minimale entre la barre [i] et la barre [j]. Commencez à remplir la masortingce à partir de rectangles de largeur 1.

 public int solution1(int[] height) { int n = height.length; if(n == 0) return 0; int[][] dp = new int[n][n]; int max = Integer.MIN_VALUE; for(int width = 1; width <= n; width++){ for(int l = 0; l+width-1 < n; l++){ int r = l + width - 1; if(width == 1){ dp[l][l] = height[l]; max = Math.max(max, dp[l][l]); } else { dp[l][r] = Math.min(dp[l][r-1], height[r]); max = Math.max(max, dp[l][r] * width); } } } return max; } 

Solution 2: programmation dynamic + 2 tableaux en cache .

time: O (n ^ 2), espace: O (n)

Idée de base: cette solution est comme la solution 1, mais permet d’économiser de l’espace. L'idée est que dans la solution 1, nous construisons la masortingce de la ligne 1 à la ligne n. Mais à chaque itération, seule la ligne précédente consortingbue à la construction de la ligne en cours. Nous utilisons donc deux tableaux comme ligne précédente et ligne actuelle.

 public int Solution2(int[] height) { int n = height.length; if(n == 0) return 0; int max = Integer.MIN_VALUE; // dp[0] and dp[1] take turns to be the "previous" line. int[][] dp = new int[2][n]; for(int width = 1; width <= n; width++){ for(int l = 0; l+width-1 < n; l++){ if(width == 1){ dp[width%2][l] = height[l]; } else { dp[width%2][l] = Math.min(dp[1-width%2][l], height[l+width-1]); } max = Math.max(max, dp[width%2][l] * width); } } return max; } 

Solution 3: utilisez la stack .

time: O (n), espace: O (n)

Cette solution est délicate et j'ai appris à le faire à partir d' explications sans graphiques et d' explications avec des graphiques . Je vous suggère de lire les deux liens avant de lire mon explication ci-dessous. C'est difficile à expliquer sans graphiques, donc mes explications pourraient être difficiles à suivre.

Voici mes explications:

1. Pour chaque barre, il faut pouvoir trouver le plus grand rectangle contenant cette barre. Donc, le plus grand de ces n rectangles est ce que nous voulons.

2. Pour obtenir le plus grand rectangle d'une certaine barre (disons bar [i], la (i + 1) ième barre), il suffit de trouver le plus grand intervalle contenant cette barre. Ce que nous soaps, c'est que toutes les barres de cet intervalle doivent avoir au moins la même hauteur avec la barre [i]. Donc, si nous trouvons combien de barres consécutives de même hauteur ou plus haut se trouvent sur la gauche immédiate de la barre [i], et combien de barres consécutives de même hauteur ou plus sont-elles à droite de la barre [ i], nous connaîtrons la longueur de l'intervalle, qui est la largeur du plus grand rectangle pour la barre [i].

3. Pour compter le nombre de barres consécutives de même hauteur ou plus haut à gauche de la barre [i], il suffit de trouver la barre la plus proche de gauche, plus courte que la barre [i], car toutes les barres entre cette barre et cette barre [i] seront des barres consécutives de même hauteur ou plus haut.

4. Nous utilisons une stack pour suivre de manière dynamic toutes les barres de gauche qui sont plus courtes que certaines barres. En d'autres termes, si nous parcourons la première barre jusqu'à la barre [i], lorsque nous arrivons à la barre [i] et que nous n'avons pas mis à jour la stack, la stack doit stocker toutes les barres ne dépassant pas la barre [i -1], y compris la barre [i-1] elle-même. Nous comparons la hauteur de la barre [i] avec chaque barre de la stack jusqu'à ce que nous en trouvions une plus courte que la barre [i], qui est la barre la plus courte du cloître. Si la barre [i] est supérieure à toutes les barres de la stack, cela signifie que toutes les barres à gauche de la barre [i] sont supérieures à la barre [i].

5. Nous pouvons faire la même chose du côté droit de la i-ème barre. Ensuite, nous soaps pour bar [i] combien de barres sont présentes dans l'intervalle.

    public int solution3(int[] height) { int n = height.length; if(n == 0) return 0; Stack left = new Stack(); Stack right = new Stack(); int[] width = new int[n];// widths of intervals. Arrays.fill(width, 1);// all intervals should at least be 1 unit wide. for(int i = 0; i < n; i++){ // count # of consecutive higher bars on the left of the (i+1)th bar while(!left.isEmpty() && height[i] <= height[left.peek()]){ // while there are bars stored in the stack, we check the bar on the top of the stack. left.pop(); } if(left.isEmpty()){ // all elements on the left are larger than height[i]. width[i] += i; } else { // bar[left.peek()] is the closest shorter bar. width[i] += i - left.peek() - 1; } left.push(i); } for (int i = n-1; i >=0; i--) { while(!right.isEmpty() && height[i] <= height[right.peek()]){ right.pop(); } if(right.isEmpty()){ // all elements to the right are larger than height[i] width[i] += n - 1 - i; } else { width[i] += right.peek() - i - 1; } right.push(i); } int max = Integer.MIN_VALUE; for(int i = 0; i < n; i++){ // find the maximum value of all rectangle areas. max = Math.max(max, width[i] * height[i]); } return max; } 

Implémentation en Python de la réponse O (n) de la réponse @ IVlad :

 from collections import namedtuple Info = namedtuple('Info', 'start height') def max_rectangle_area(histogram): """Find the area of the largest rectangle that fits entirely under the histogram. """ stack = [] top = lambda: stack[-1] max_area = 0 pos = 0 # current position in the histogram for pos, height in enumerate(histogram): start = pos # position where rectangle starts while True: if not stack or height > top().height: stack.append(Info(start, height)) # push elif stack and height < top().height: max_area = max(max_area, top().height*(pos-top().start)) start, _ = stack.pop() continue break # height == top().height goes here pos += 1 for start, height in stack: max_area = max(max_area, height*(pos-start)) return max_area 

Exemple:

 >>> f = max_rectangle_area >>> f([5,3,1]) 6 >>> f([1,3,5]) 6 >>> f([3,1,5]) 5 >>> f([4,8,3,2,0]) 9 >>> f([4,8,3,1,1,0]) 9 

Recherche linéaire à l'aide d'une stack de sous-problèmes incomplets

Copier-coller la description de l'algorithme (au cas où la page tombe en panne):

Nous traitons les éléments dans l'ordre de gauche à droite et maintenons une stack d'informations sur les sous-histogrammes démarrés mais non encore terminés. Chaque fois qu'un nouvel élément arrive, il est soumis aux règles suivantes. Si la stack est vide, nous ouvrons un nouveau sous-problème en poussant l'élément sur la stack. Sinon, nous le comparons à l'élément en haut de la stack. Si le nouveau est plus grand, nous le repoussons à nouveau. Si le nouveau est égal, nous le sautons. Dans tous ces cas, nous continuons avec le nouvel élément suivant. Si le nouveau est inférieur, nous terminons le sous-problème le plus haut en mettant à jour la zone maximale par rapport à l'élément situé en haut de la stack. Ensuite, nous supprimons l'élément en haut et répétons la procédure en conservant le nouvel élément actuel. De cette façon, tous les sous-problèmes sont terminés jusqu'à ce que la stack soit vide ou que son élément supérieur soit inférieur ou égal au nouvel élément, menant aux actions décrites ci-dessus. Si tous les éléments ont été traités et que la stack n'est pas encore vide, nous terminons les sous-problèmes restants en mettant à jour la zone maximale par rapport aux éléments du haut.

Pour la mise à jour par rapport à un élément, nous trouvons le plus grand rectangle qui inclut cet élément. Notez qu'une mise à jour de la zone maximale est effectuée pour tous les éléments à l'exception de ceux ignorés. Si un élément est ignoré, il possède cependant le même plus grand rectangle que l'élément situé en haut de la stack, qui sera mis à jour ultérieurement. La hauteur du plus grand rectangle est bien entendu la valeur de l'élément. Au moment de la mise à jour, on sait à quel point le plus grand rectangle s'étend à droite de l'élément, car alors, pour la première fois, un nouvel élément de plus petite hauteur est arrivé. L'information, à quelle distance le plus grand rectangle s'étend à gauche de l'élément, est disponible si nous la stockons également dans la stack.

Nous révisons donc la procédure décrite ci-dessus. Si un nouvel élément est poussé immédiatement, soit parce que la stack est vide, soit plus haut que l'élément supérieur de la stack, le plus grand rectangle le contenant ne s'étend pas plus loin que l'élément actuel. S'il est poussé après que plusieurs éléments aient été sortis de la stack, car il est inférieur à ces éléments, le plus grand rectangle le contenant s'étend vers la gauche jusqu'à celui du dernier élément sauté.

Chaque élément est poussé et éclaté au plus une fois et à chaque étape de la procédure, au moins un élément est poussé ou sauté. Comme la quantité de travail pour les décisions et la mise à jour est constante, la complexité de l’algorithme est O (n) par parsing amortie.

La solution la plus simple dans O (N)

 long long getMaxArea(long long hist[], long long n) { stack s; long long max_area = 0; long long tp; long long area_with_top; long long i = 0; while (i < n) { if (s.empty() || hist[s.top()] <= hist[i]) s.push(i++); else { tp = s.top(); // store the top index s.pop(); // pop the top area_with_top = hist[tp] * (s.empty() ? i : i - s.top() - 1); if (max_area < area_with_top) { max_area = area_with_top; } } } while (!s.empty()) { tp = s.top(); s.pop(); area_with_top = hist[tp] * (s.empty() ? i : i - s.top() - 1); if (max_area < area_with_top) max_area = area_with_top; } return max_area; } 

Les autres réponses ici ont fait un excellent travail en présentant la solution O (n) -time, O (n) -space en utilisant deux stacks. Il y a une autre perspective sur ce problème qui fournit indépendamment une solution O (n) -time, O (n) -space au problème, et pourrait fournir un peu plus de détails sur le fonctionnement de la solution basée sur la stack.

L’idée principale est d’utiliser une structure de données appelée arbre cartésien . Un arbre cartésien est une structure d’arbre binary (mais pas une arborescence de recherche binary) construite autour d’un tableau d’entrée. Plus précisément, la racine de l’arbre cartésien est construite au-dessus de l’élément minimum du tableau, et les sous-arbres gauche et droit sont construits récursivement à partir des sous-réseaux situés à gauche et à droite de la valeur minimale.

Par exemple, voici un exemple de tableau et son arbre cartésien:

  +----------------------- 23 ------+ | | +------------- 26 --+ +-- 79 | | | 31 --+ 53 --+ 84 | | 41 --+ 58 -------+ | | 59 +-- 93 | 97 +----+----+----+----+----+----+----+----+----+----+----+ | 31 | 41 | 59 | 26 | 53 | 58 | 97 | 93 | 23 | 84 | 79 | +----+----+----+----+----+----+----+----+----+----+----+ 

La raison pour laquelle les arbres cartésiens sont utiles dans ce problème est que la question à l’examen a une structure vraiment récursive. Commencez par regarder le rectangle le plus bas de l’histogramme. Il y a trois options pour l’endroit où le rectangle maximum pourrait être placé:

• Il pourrait passer juste sous la valeur minimale de l’histogramme. Dans ce cas, pour le rendre le plus grand possible, nous voudrions le rendre aussi large que le tableau entier.

• Il pourrait être entièrement à gauche de la valeur minimale. Dans ce cas, nous voulons récursivement que la réponse formée à partir du sous-tableau soit purement à gauche de la valeur minimale.

• Il pourrait être entièrement à la droite de la valeur minimale. Dans ce cas, nous voulons récursivement que la réponse formée à partir du sous-tableau soit purement à droite de la valeur minimale.

Notez que cette structure récursive – trouvez la valeur minimale, faites quelque chose avec les sous-réseaux à gauche et à droite de cette valeur – correspond parfaitement à la structure récursive d’un arbre cartésien. En fait, si nous pouvons créer un arbre cartésien pour l’ensemble du tableau lorsque nous commençons, nous pouvons alors résoudre ce problème en marchant récursivement l’arbre cartésien de la racine vers le bas. À chaque point, nous calculons récursivement le rectangle optimal dans les sous-réseaux gauche et droit, ainsi que le rectangle obtenu en ajustant juste sous la valeur minimale, puis nous renvoyons la meilleure option trouvée.

En pseudocode, cela ressemble à ceci:

 function largestRectangleUnder(int low, int high, Node root) { /* Base case: If the range is empty, the biggest rectangle we * can fit is the empty rectangle. */ if (low == high) return 0; /* Assume the Cartesian tree nodes are annotated with their * positions in the original array. */ return max { (high - low) * root.value, // Widest rectangle under the minimum largestRectangleUnder(low, root.index, root.left), largestRectnagleUnder(root.index + 1, high, root.right) } } 

Une fois que nous avons l’arbre cartésien, cet algorithme prend du temps O (n), puisque nous visitons chaque nœud exactement une fois et faisons O (1) travailler par nœud.

Il s’avère qu’il existe un algorithme simple, à temps linéaire, pour la construction d’arbres cartésiens. La façon “naturelle” de penser à en construire un serait de parcourir le tableau, de trouver la valeur minimale, puis de construire récursivement un arbre cartésien à partir des sous-tableaux de gauche et de droite. Le problème est que le processus de recherche de la valeur minimale est très coûteux et cela peut prendre du temps Θ (n ² ).

La méthode rapide pour créer un arbre cartésien consiste à balayer le tableau de gauche à droite, en ajoutant un élément à la fois. Cet algorithme est basé sur les observations suivantes sur les arbres cartésiens:

• Premièrement, les arbres cartésiens obéissent à la propriété heap: chaque élément est inférieur ou égal à ses enfants. La raison en est que la racine de l’arbre cartésien est la plus petite valeur du tableau global et que ses enfants sont les plus petits éléments de leurs sous-réseaux, etc.

• Deuxièmement, si vous effectuez une traversée inordonnée d’un arbre cartésien, vous récupérez les éléments du tableau dans l’ordre dans lequel ils apparaissent. Pour voir pourquoi cela se produit, notez que si vous effectuez une traversée inordonnée d’un arbre cartésien, vous visitez d’abord tout ce qui se trouve à gauche de la valeur minimale, puis la valeur minimale, puis tout ce qui se trouve à droite de la valeur minimale. Ces visites sont effectuées de manière récursive de la même manière, donc tout finit par être visité dans l’ordre.

Ces deux règles nous donnent beaucoup d’informations sur ce qui se passe si nous commençons avec un arbre cartésien des k premiers éléments du tableau et voulons former un arbre cartésien pour les premiers k + 1 éléments. Ce nouvel élément devra se retrouver sur la colonne vertébrale droite de l’arbre cartésien – la partie de l’arbre formée en commençant à la racine et en ne faisant que des pas vers la droite – sinon, quelque chose le suivrait dans une traversée inordonnée. Et, à l’intérieur de cette colonne vertébrale, il doit être placé d’une manière qui le rend plus grand que tout ce qui est au-dessus, puisque nous devons obéir à la propriété tas.

La façon dont vous ajoutez un nouveau nœud à l’arborescence cartésienne consiste à démarrer au nœud le plus à droite de l’arborescence et à remonter jusqu’à ce que vous atteigniez la racine de l’arborescence ou que vous trouviez un nœud de valeur inférieure. Vous faites ensuite en sorte que la nouvelle valeur ait comme enfant gauche le dernier nœud sur lequel elle est montée.

Voici une trace de cet algorithme sur un petit tableau:

 +---+---+---+---+ | 2 | 4 | 3 | 1 | +---+---+---+---+ 

2 devient la racine.

  2 --+ | 4 

4 est plus grand que 2, nous ne pouvons pas nous déplacer vers le haut. Ajouter à droite.

 +---+---+---+---+ | 2 | 4 | 3 | 1 | +---+---+---+---+ 2 ------+ | --- 3 | 4 

3 est inférieur à 4, grimpez dessus. Ne peut pas monter plus de 2, car il est inférieur à 3. Escaladé sur le sous-arbre enraciné à 4 va à gauche de la nouvelle valeur 3 et 3 devient le nœud le plus à droite maintenant.

 +---+---+---+---+ | 2 | 4 | 3 | 1 | +---+---+---+---+ +---------- 1 | 2 ------+ | --- 3 | 4 

1 monte au-dessus de la racine 2, l’arbre entier qui est enraciné à 2 est déplacé à gauche de 1, et 1 est maintenant la nouvelle racine – et aussi la valeur la plus à droite.

 +---+---+---+---+ | 2 | 4 | 3 | 1 | +---+---+---+---+ 

Bien que cela puisse ne pas sembler fonctionner dans le temps linéaire – ne finiriez-vous pas par grimper jusqu’à la racine de l’arbre, encore et encore? – Vous pouvez montrer que cela fonctionne en temps linéaire en utilisant un argument intelligent. Si vous montez sur un nœud dans la colonne vertébrale lors d’une insertion, ce nœud finit par être déplacé de la colonne vertébrale droite et ne peut donc pas être réanalysé lors d’une insertion ultérieure. Par conséquent, chaque nœud n’est analysé qu’une seule fois, le travail total est donc linéaire.

Et maintenant, le kicker – la méthode standard pour implémenter cette approche est de conserver une stack de valeurs qui correspondent aux nœuds de la colonne vertébrale droite. Le fait de «monter» et de survoler un nœud correspond à l’extinction d’un nœud de la stack. Par conséquent, le code pour construire un arbre cartésien ressemble à ceci:

 Stack s; for (each array element x) { pop s until it's empty or s.top > x push x onto the stack. do some sort of pointer rewiring based on what you just did. 

Voici un code Java qui implémente cette idée, gracieuseté de @Azeem!

 import java.util.Stack; public class CartesianTreeMakerUtil { private static class Node { int val; Node left; Node right; } public static Node cartesianTreeFor(int[] nums) { Node root = null; Stack s = new Stack<>(); for(int curr : nums) { Node lastJumpedOver = null; while(!s.empty() && s.peek().val > curr) { lastJumpedOver = s.pop(); } Node currNode = this.new Node(); currNode.val = curr; if(s.isEmpty()) { root = currNode; } else { s.peek().right = currNode; } currNode.left = lastJumpedOver; s.push(currNode); } return root; } public static void printInOrder(Node root) { if(root == null) return; if(root.left != null ) { printInOrder(root.left); } System.out.println(root.val); if(root.right != null) { printInOrder(root.right); } } public static void main(Ssortingng[] args) { int[] nums = new int[args.length]; for (int i = 0; i < args.length; i++) { nums[i] = Integer.parseInt(args[i]); } Node root = cartesianTreeFor(nums); tester.printInOrder(root); } } 

Les manipulations de la stack peuvent vous sembler familières, et c'est parce que ce sont les opérations exactes que vous feriez dans les réponses affichées ici. En fait, vous pouvez penser à ce que font ces approches en construisant implicitement l'arbre cartésien et en exécutant l'algorithme récursif illustré ci-dessus.

Je pense que l'avantage de connaître les arbres cartésiens réside dans le fait qu'il fournit un cadre conceptuel vraiment intéressant pour voir pourquoi cet algorithme fonctionne correctement. Si vous savez que vous exécutez une marche récursive d'un arbre cartésien, il est plus facile de voir que vous êtes assuré de trouver le plus grand rectangle. De plus, savoir que l’arbre cartésien existe vous donne un outil utile pour résoudre d’autres problèmes. Les arborescences cartésiennes apparaissent dans la conception de structures de données rapides pour le problème de requête de plage minimale et sont utilisées pour convertir des tableaux de suffixes en arborescences de suffixes .

Il existe également une autre solution utilisant Divide and Conquer. L’algorithme pour cela est:

1) Diviser le tableau en 2 parties avec la plus petite hauteur comme sharepoint rupture

2) La surface maximale est le maximum de: a) la plus petite hauteur * la taille du tableau b) le rectangle maximum dans la moitié gauche du tableau c) le rectangle maximum dans la moitié du tableau droit

La complexité du temps vient à O (nlogn)

La solution de stack est l’une des solutions les plus intelligentes que j’ai vues à ce jour. Et il peut être difficile de comprendre pourquoi cela fonctionne.

J’ai pris un jab pour expliquer la même chose en détail ici .

Résumé des points du post: –

• Manière générale notre cerveau pense: –
  • Créez chaque situation et essayez de trouver la valeur de la contraint nécessaire pour résoudre le problème.
  • Et nous sums heureux de convertir ce code en: – trouver la valeur de contraint (min) pour chaque situation (paire (i, j))

Les solutions intelligentes tentent de retourner le problème. Pour chaque valeur de constraint/min de l’aire, quel est le meilleur extrême gauche et droit possible?

• Donc, si nous parcourons chaque min possible dans le tableau. Quels sont les extrêmes gauche et droit pour chaque valeur?

  • Peu de pensée dit, la première valeur la plus à gauche est inférieure à la valeur minimale current min et la première valeur la plus à droite est inférieure à la valeur actuelle min.

• Nous devons donc maintenant voir si nous pouvons trouver une manière intelligente de trouver les premières valeurs de gauche et de droite inférieures à la valeur actuelle.

• Penser : Si nous avons parcouru partiellement le tableau jusqu’à min_i, comment peut-on construire la solution min_i + 1?

• Nous avons besoin de la première valeur inférieure à min_i à sa gauche.

• Inverser l’instruction: il faut ignorer toutes les valeurs à gauche de min_i supérieures à min_i. Nous nous arrêtons lorsque nous trouvons la première valeur inférieure à min_i (i). Les creux dans la courbe deviennent donc inutiles une fois que nous l’avons traversée . Dans l’histogramme, (2 4 3) => si 3 est min_i, 4 étant plus grand n’est pas intéressant.
• Corrollary : dans une gamme (i, j). j étant la valeur minimale que nous considérons. Toutes les valeurs entre j et sa valeur de gauche sont inutiles. Même pour des calculs ultérieurs.
• Tout histogramme à droite avec une valeur min plus grande que j sera lié à j. Les valeurs d’intérêt à gauche forment une séquence monotone croissante avec j la plus grande valeur. (Les valeurs d’intérêt ici étant des valeurs possibles susceptibles d’intéresser le tableau suivant)
• Puisque nous voyageons de gauche à droite, pour chaque valeur minimale / valeur actuelle, nous ne soaps pas si le côté droit du tableau aura un élément plus petit que celui-ci.
  • Nous devons donc le garder en mémoire jusqu’à ce que nous sachions que cette valeur est inutile. (car une plus petite valeur est trouvée)

• Tout cela conduit à une utilisation de notre propre structure de stack .

  • Nous restons sur la stack jusqu’à ce que nous ne sachions rien d’inutile.
  • Nous retirons de la stack une fois que nous soaps que la chose est de la merde.

• Donc, pour chaque valeur min pour trouver sa valeur plus petite gauche, nous faisons ce qui suit: –

  1. pop les éléments plus grands (valeurs inutiles)
  2. Le premier élément plus petit que la valeur est l’extrême gauche. Le i à notre min.
• Nous pouvons faire la même chose du côté droit du tableau et nous aurons j pour notre min.

C’est assez difficile à expliquer, mais si cela a du sens, je suggère de lire l’article complet ici, car il contient plus de détails et d’informations.

Je ne comprends pas les autres entrées, mais je pense savoir comment le faire dans O (n) comme suit.

A) pour chaque index, trouvez le plus grand rectangle à l’intérieur de l’histogramme se terminant à cet index où la colonne d’index touche le haut du rectangle et mémorisez où le rectangle commence. Cela peut être fait dans O (n) en utilisant un algorithme basé sur la stack.

B) De même, pour chaque index, recherchez le plus grand rectangle commençant à cet index, où la colonne d’index touche le haut du rectangle et se rappelle où le rectangle se termine. Aussi O (n) en utilisant la même méthode que (A) mais en balayant l’histogramme vers l’arrière.

C) Pour chaque index, combinez les résultats de (A) et (B) pour déterminer le plus grand rectangle où la colonne à cet index touche le haut du rectangle. O (n) comme (A).

D) Le plus grand rectangle devant être touché par une colonne de l’histogramme, le plus grand rectangle est le plus grand rectangle trouvé à l’étape (C).

La partie difficile est la mise en œuvre de (A) et (B), ce que JF Sebastian a peut-être résolu plutôt que le problème général énoncé.

J’ai codé celui-ci et je me sentais un peu mieux dans le sens:

 import java.util.Stack; class StackItem{ public int sup; public int height; public int sub; public StackItem(int a, int b, int c){ sup = a; height = b; sub =c; } public int getArea(){ return (sup - sub)* height; } @Override public Ssortingng toSsortingng(){ return " from:"+sup+ " to:"+sub+ " height:"+height+ " Area ="+getArea(); } } public class MaxRectangleInHistogram { Stack S; StackItem curr; StackItem maxRectangle; public StackItem getMaxRectangleInHistogram(int A[], int n){ int i = 0; S = new Stack(); S.push(new StackItem(0,0,-1)); maxRectangle = new StackItem(0,0,-1); while(i S.peek().height){ S.push(curr); }else if(curr.height == S.peek().height){ S.peek().sup = i+1; }else if(curr.height < S.peek().height){ while((S.size()>1) && (curr.height<=S.peek().height)){ curr.sub = S.peek().sub; S.peek().sup = i; decideMaxRectangle(S.peek()); S.pop(); } S.push(curr); } i++; } while(S.size()>1){ S.peek().sup = i; decideMaxRectangle(S.peek()); S.pop(); } return maxRectangle; } private void decideMaxRectangle(StackItem s){ if(s.getArea() > maxRectangle.getArea() ) maxRectangle = s; } } 

Juste noter:

 Time Complexity: T(n) < O(2n) ~ O(n) Space Complexity S(n) < O(n) 

Vous pouvez utiliser la méthode O (n) qui utilise stack pour calculer la surface maximale sous l’histogramme.

 long long histogramArea(vector &histo){ stack s; long long maxArea=0; long long area= 0; int i =0; for (i = 0; i < histo.size();) { if(s.empty() || histo[s.top()] <= histo[i]){ s.push(i++); } else{ int top = s.top(); s.pop(); area= histo[top]* (s.empty()?i:is.top()-1); if(area >maxArea) maxArea= area; } } while(!s.empty()){ int top = s.top();s.pop(); area= histo[top]* (s.empty()?i:is.top()-1); if(area >maxArea) maxArea= area; } return maxArea; } 

Pour des explications, vous pouvez lire ici http://www.geeksforgeeks.org/largest-rectangle-under-histogram/

Je voudrais remercier @templatetypedef pour sa réponse extrêmement détaillée et intuitive. Le code Java ci-dessous est basé sur sa suggestion d’utiliser des arbres cartésiens et résout le problème dans le temps O (N) et l’espace O (N). Je vous suggère de lire la réponse de @ templatetypedef ci-dessus avant de lire le code ci-dessous. Le code est donné dans le format de la solution au problème à leetetcode: https://leetcode.com/problems/largest-rectangle-in-histogram/description/ et passe tous les 96 cas de test.

 class Solution { private class Node { int val; Node left; Node right; int index; } public Node getCartesianTreeFromArray(int [] nums) { Node root = null; Stack s = new Stack<>(); for(int i = 0; i < nums.length; i++) { int curr = nums[i]; Node lastJumpedOver = null; while(!s.empty() && s.peek().val >= curr) { lastJumpedOver = s.pop(); } Node currNode = this.new Node(); currNode.val = curr; currNode.index = i; if(s.isEmpty()) { root = currNode; } else { s.peek().right = currNode; } currNode.left = lastJumpedOver; s.push(currNode); } return root; } public int largestRectangleUnder(int low, int high, Node root, int [] nums) { /* Base case: If the range is empty, the biggest rectangle we * can fit is the empty rectangle. */ if(root == null) return 0; if (low == high) { if(0 <= low && low <= nums.length - 1) { return nums[low]; } return 0; } /* Assume the Cartesian tree nodes are annotated with their * positions in the original array. */ int leftArea = -1 , rightArea= -1; if(root.left != null) { leftArea = largestRectangleUnder(low, root.index - 1 , root.left, nums); } if(root.right != null) { rightArea = largestRectangleUnder(root.index + 1, high,root.right, nums); } return Math.max((high - low + 1) * root.val, Math.max(leftArea, rightArea)); } public int largestRectangleArea(int[] heights) { if(heights == null || heights.length == 0 ) { return 0; } if(heights.length == 1) { return heights[0]; } Node root = getCartesianTreeFromArray(heights); return largestRectangleUnder(0, heights.length - 1, root, heights); } 

}