Maior retângulo no histograma
Guia detalhado e implementação de Python para o problema do 'Maior retângulo no histograma'.
1. Aprenda
O problema do 'Maior retângulo no histograma' é um desafio importante na seção Pilha.
Esta implementação concentra-se na lógica de nível fácil em Python.
Priorizamos a precisão técnica e a legibilidade do código em nossas soluções fornecidas.
2. Real-World Applications
3. Visual Intuition
Visualizando o fluxo lógico para o maior retângulo do histograma.
4. Prerequisites
5. Step-by-Step Thinking
1. Understand the problem
Leia atentamente a definição do problema para o maior retângulo do histograma.
2. Formulate brute force
Elabore uma solução iterativa simples.
3. Identify inefficiency
Procure cálculos redundantes.
4. Optimize search path
Use hashing ou classificação para acelerar o processo.
5. Final Implementation
Limpe o código para padrões de produção.
Declaração do problema
Dada uma matriz de inteiros heights representando a altura da barra do histograma, onde a largura de cada barra é 1, retorne a área do maior retângulo no histograma.
Escreva uma função largestRectangleArea(heights: List[int]) -> int.
- •1 <= len(heights) <= 10^5
- •0 <= heights[i] <= 10^4
Exemplos
heights = [2, 1, 5, 6, 2, 3]
10
The largest rectangle has area 10, formed by bars at index 2 and 3 (heights 5 and 6), with width 2 and height 5.
heights = [2, 4]
4
The largest rectangle is the bar at index 1 with height 4 and width 1, giving area 4.
Need a Hint?
Edge Cases to Watch
- Estruturas de entrada vazias
- Entradas de elemento único
- Grandes limites numéricos
Pronto para resolver?
Open the problem in PyRun's browser-based Python editor. Your code runs fully offline — no server required.
Insights e variações da entrevista
Análise de complexidade
Por que tempo: Directly evaluates all possibilities.
Por que espaço: Uses standard local memory.
Por que tempo: Optimized paths reduce total operations.
Por que espaço: May trade memory for speed.
Código Python da solução otimizada
Código Python da solução otimizada
def largest_rectangle_opt(heights):
maxArea = 0
stack = [] # index, height
for i, h in enumerate(heights):
start = i
while stack and stack[-1][1] > h:
index, height = stack.pop()
maxArea = max(maxArea, height * (i - index))
start = index
stack.append((start, h))
for i, h in stack:
maxArea = max(maxArea, h * (len(heights) - i))
return maxAreaCódigo de força bruta (protegido por spoiler)
Código de força bruta (protegido por spoiler)
def largest_rectangle_brute(heights):
max_area = 0
for i in range(len(heights)):
min_h = heights[i]
for j in range(i, len(heights)):
min_h = min(min_h, heights[j])
max_area = max(max_area, min_h * (j - i + 1))
return max_areaAlgorithm Pattern Checklist
When dealing with Stack data patterns.
- Are constraints clear?
- Is there a linear or logarithmic optimization possible?
Key Revision Notes
Aplicam-se propriedades de problema de pilha padrão.
Perguntas relacionadas
PyRun is built and maintained by an independent solo developer. If this helped your interview prep, consider buying a coffee!
Recursos Python recomendados
Expanda seu conhecimento com tutoriais interativos relacionados, folhas de dicas e comparações de código.
Tentativa/Exceção em Python e tratamento de erros
Evite que seus scripts Python travem. Aprenda os blocos try, exceto, finalmente e como gerar exceções personalizadas corretamente.
Como reverter uma string em Python
Aprenda como reverter uma string em Python usando fatiamento, a função reversed() e concatenação de loop com exemplos de código visual.
Folha de dicas dos métodos de string Python
Um guia de referência completo para manipulação de strings em Python. Domine a formatação, pesquisa, divisão, substituição e verificação de propriedades de string.
Python vs JavaScript: qual linguagem de programação é a melhor?
Uma comparação abrangente entre Python e JavaScript. Explore diferenças de sintaxe, desempenho, casos de uso (backend versus frontend) e exemplos de codificação.