Container With Most Water

Enunciado do problema

Dados n inteiros não negativos a1, a2, …, an, onde cada um representa um ponto na coordenada (i, ai). n linhas verticais são desenhadas de tal forma que os dois pontos finais da linha i estão em (i, ai) e (i, 0). Encontre duas linhas, que, juntamente com o eixo x, formam um contêiner, de modo que o contêiner contenha a maior quantidade de água.

Nota: Você não pode inclinar o recipiente e n é pelo menos 2.

Solução

A área é dependente da distância entre as duas alturas e a altura mínima entre as duas. É possível controlar de forma linear a distância entre as alturas, partindo de um ponto onde a maior distância é selecionada e reduzi-lo ao longo do tempo.

A maior distância possível entre alturas pode ser encontrada usando dois ponteiros, um no início do array e outro no final. Calcule a área e reduza a distância. Para encolher de forma ideal, selecione o ponteiro que tenha o menor valor e mova-o para o meio. O loop ocorre enquanto a posição dos ponteiros é diferente.

int maxArea(vector<int>& height) {
    int start=0,end=height.size()-1,maxArea=0,area;

    while(start<end){
        area = min(height[start],height[end])*(end-start);
        maxArea = max(maxArea,area);

        if(height[start]>height[end]){
            end--;
        }else
            start++;
    }

    return maxArea;
}

Complexidade de tempo: O(n)

Complexidade de espaço: O(1)

question from LeetCode