Recursão no final das contas é um processo iterativo que ao invés de usar um contador/sentinela/flag seja lá o nome que vc quiser dar, usa a pilha de invocação para “controlar” o processo de repetição que deve cessar em um ou mais casos base ou repetir em um ou mais casos recursivos/indutivos/recorrentes. Claro, recursão para os “não iniciados” parece um bicho de sete cabeças, ainda mais quando você quer, a partir do caso base alcançado em uma cadeia mais profunda de chamadas recursivas, que o valor gerado no caso em questão seja propagado para a base da pilha. É difícil de enxergar o caminho dos retornos eu quero dizer.
Como curiosidade, uma solução recursiva seria assim (também testei na plataforma e foi aceita):
class Solution {
private static class MaiorArea {
int valor;
}
public int maxArea(int[] height) {
MaiorArea maiorArea = new MaiorArea();
maxAreaRec( height, 0, height.length - 1, maiorArea );
return maiorArea.valor;
}
private void maxAreaRec( int[] height, int esquerda, int direita, MaiorArea maiorArea ) {
if ( esquerda < direita ) {
int altEsquerda = height[esquerda];
int altDireita = height[direita];
int area = Math.min( altEsquerda, altDireita ) * ( direita - esquerda );
if ( maiorArea.valor < area ) {
maiorArea.valor = area;
}
if ( altEsquerda < altDireita ) {
maxAreaRec( height, esquerda + 1, direita, maiorArea );
} else {
maxAreaRec( height, esquerda, direita - 1, maiorArea );
}
}
}
}
Como não temos ponteiros em Java, uma solução para armazenar o valor é usar uma classe interna como eu fiz. Vou tentar fazer sem o uso da classe. Se tiver sucesso atualizo aqui.
Normalmente essas plataformas esperam resultados generalizados e sempre tem os “corner cases”/casos patológicos para atrapalhar. Sobre o recrutador, provavelmente ele resolveu o problema antes. Eu seleciono alunos para monitoria usando desafios de programação que se encaixam no que eles já conhecem. É super efetivo.
ATUALIZAÇÃO
Segue a solução recursiva sem a classe interna:
class Solution {
public int maxArea(int[] height) {
return maxAreaRec( height, 0, height.length - 1, 0 );
}
private int maxAreaRec( int[] height, int esquerda, int direita, int maiorArea ) {
if ( esquerda < direita ) {
int altEsquerda = height[esquerda];
int altDireita = height[direita];
int area = Math.min( altEsquerda, altDireita ) * ( direita - esquerda );
if ( maiorArea < area ) {
maiorArea = area;
}
if ( altEsquerda < altDireita ) {
return maxAreaRec( height, esquerda + 1, direita, maiorArea );
} else {
return maxAreaRec( height, esquerda, direita - 1, maiorArea );
}
}
return maiorArea;
}
}
Note também que sempre que for possível se usar estruturas iterativas ao invés de recursão, procure usar iteração, visto que com recursão a ordem de complexidade relativa ao espaço vai fatalmente piorar. Na versão iterativa desse problema, temos algo como O(1), enquanto na recursiva temos O(n). Em relação ao tempo, ambas são O(n). Como comparativo, nas minhas três submissões eu obtive os seguintes resultados nos tempos de execução:
- Iterativo: 3ms
- Recursivo com a classe interna: 16ms
- Recursivo sem a classe interna: 13ms
No uso de memória, também como se espera, a versão iterativa usou 10MB a menos. Pelo uso de memória e pela quantidade de tempo, é quase certeza que são executados diversos testes ou então um teste bem grande, visto que o domínio da função varia de 2 a 10^5 e as alturas variam de 0 a 10^4.
