_Créditos das imagens: ChatGPT_
# LeetCode :: Container With Most Water (Harbour & TLPP)
O problema [**"Container With Most Water"**](https://leetcode.com/problems/container-with-most-water/), do LeetCode, requer encontrar o maior volume de água que pode ser contido entre duas linhas verticais em um gráfico. O desafio está em otimizar a busca para que a solução seja eficiente, preferencialmente em \(O(n)\).
### Descrição do Problema
Dado um array de inteiros \(height\), onde cada elemento representa a altura de uma linha vertical no gráfico:
1. Escolha duas linhas para formar as paredes de um contêiner.
2. O volume de água que o contêiner pode conter é determinado pelo menor dos dois valores entre as alturas escolhidas multiplicado pela distância entre elas.
O objetivo é retornar o maior volume de água que pode ser armazenado.
### Exemplo
Para \(height = [1,8,6,2,5,4,8,3,7]\):
- O maior volume de água possível é \(49\), formado pelas alturas \(8\) e \(7\), com distância \(7\).
---
### Solução Otimizada em \(O(n)\)
A abordagem ideal utiliza dois ponteiros (um no início e outro no final do array) que convergem para o centro, maximizando o volume durante a busca.
#### Passos:
1. Inicialize dois ponteiros: um no início (\(i = 0\)) e outro no final (\(j = n-1\)).
2. Calcule o volume do contêiner formado pelas alturas \(height[i]\) e \(height[j]\).
3. Atualize o maior volume encontrado.
4. Mova o ponteiro correspondente à menor altura (para tentar encontrar uma altura maior).
5. Repita até que os ponteiros se encontrem.
---
### Implementação em Harbour & TLPP
1. Versão 1: Loop while.
2. Versão 2: Loop for.
3. Versão 3: Loop com aEval.
Aqui (👇) estão as implementações desse algoritmo em Harbour:
[container.with.most.water.11.1.prg](https://github.com/naldodj/naldodj-xbase-leetcode-solutions/blob/main/src/hb/011/container.with.most.water.11.1.prg)
[container.with.most.water.11.2.prg](https://github.com/naldodj/naldodj-xbase-leetcode-solutions/blob/main/src/hb/011/container.with.most.water.11.2.prg)
[container.with.most.water.11.3.prg](https://github.com/naldodj/naldodj-xbase-leetcode-solutions/blob/main/src/hb/011/container.with.most.water.11.3.prg)
Aqui (👇) estão as implementações desse algoritmo em TLPP:
[container.with.most.water.11.1.tlpp](https://github.com/naldodj/naldodj-xbase-leetcode-solutions/blob/main/src/tlpp/011/container.with.most.water.11.1.tlpp)
[container.with.most.water.11.2.tlpp](https://github.com/naldodj/naldodj-xbase-leetcode-solutions/blob/main/src/tlpp/011/container.with.most.water.11.2.tlpp)
[container.with.most.water.11.3.tlpp](https://github.com/naldodj/naldodj-xbase-leetcode-solutions/blob/main/src/tlpp/011/container.with.most.water.11.3.tlpp)
---
### Testando as implementações: Observe as figuras 1 e 2, abaixo.
### Explicação do Código
1. **Inicialização**:
- Os ponteiros \(nLeft\) e \(nRight\) delimitam os índices das linhas a serem comparadas.
2. **Cálculo do Volume**:
- O volume é o menor dos valores das alturas multiplicado pela distância entre os ponteiros.
3. **Movimento dos Ponteiros**:
- O ponteiro correspondente à menor altura é movido para o centro, pois aumentar a altura é mais promissor para encontrar um volume maior.
---
### Complexidade
- **Tempo**: \(O(n)\), pois cada índice é processado uma vez.
- **Espaço**: \(O(1)\), apenas variáveis auxiliares são usadas.
Vamos analisar cada caso para entender como o cálculo funciona.
---
### 1. **Input:** `[1,8,6,2,5,4,8,3,7]`
**Output:** `49`
**Expected:** `49`
**Matched:** `true`
- **Análise:**
Para o maior volume, escolhemos as alturas `8` (índice 2) e `7` (índice 9).
A distância entre as duas alturas é `9 - 2 = 7`.
O volume é dado por: `Volume = min(8, 7) * 7 = 7 * 7 = 49`
Esse é o maior volume possível para este conjunto de alturas.
---
### 1. **Input:** `[1,8,6,2,5,4,8,3,7]`
**Output:** `49`
**Expected:** `49`
**Matched:** `true`
- **Análise:**
Para o maior volume, escolhemos as alturas `8` (índice 2) e `7` (índice 9).
A distância entre as duas alturas é `9 - 2 = 7`.
O volume é dado por: `Volume = min(8, 7) * 7 = 7 * 7 = 49`
Esse é o maior volume possível para este conjunto de alturas.
---
### 2. **Input:** `[1,1]`
**Output:** `1`
**Expected:** `1`
**Matched:** `true`
- **Análise:**
Existem apenas duas linhas, ambas de altura `1`.
A distância entre elas é `1` (índice 2 - índice 1 = 1).
O volume é dado por: `Volume = min(1, 1) * 1 = 1 * 1 = 1`
Como só há duas alturas, este é o único volume possível.
---
### 3. **Input:** `[3,1,2]`
**Output:** `4`
**Expected:** `4`
**Matched:** `true`
- **Análise:**
Para o maior volume, escolhemos as alturas `3` (índice 1) e `2` (índice 3).
A distância entre elas é `3 - 1 = 2`.
O volume é dado por: `Volume = min(3, 2) * 2 = 2 * 2 = 4`
Esse é o maior volume possível.
---
### 4. **Input:** `[15,70,12,21,10,2]`
**Output:** `45`
**Expected:** `45`
**Matched:** `true`
- **Análise:**
Para o maior volume, escolhemos as alturas `15` (índice 1) e `21` (índice 4).
A distância entre elas é `4 - 1 = 3`.
O volume é dado por: `Volume = min(15, 21) * 3 = 15 * 3 = 45`
Embora a altura `70` seja maior, ela não contribui para um volume maior quando comparada com outras alturas mais próximas.
Essa afirmativa refere-se a um aspecto fundamental do problema: **o volume é limitado pela menor das duas alturas escolhidas e pela distância entre elas.** Isso significa que, mesmo que uma das alturas seja muito grande, o volume pode ser pequeno se a distância for curta ou se a outra altura for significativamente menor.
Vamos detalhar isso no contexto da entrada `[15,70,12,21,10,2]`:
---
#### Comparações usando a altura `70` (índice 2):
### 1. **Análise da Altura `70`**
- A altura `70` está no índice `2` e é, de longe, a maior do array.
- Porém, para calcular o volume, precisamos considerar:
- A menor altura entre `70` e a outra linha escolhida.
- A distância entre essas duas linhas.
---
#### Comparações usando a altura `70` (índice 2):
1. **Com `15` (índice 1):**
- Distância = `2 - 1 = 1`
- `Volume = (min(70, 15) * 1 = 15 * 1 = 15)`
2. **Com `12` (índice 3):**
- Distância = `3 - 2 = 1`
- `Volume = (min(70, 12) * 1 = 12 * 1 = 12)`
3. **Com `21` (índice 4):**
- Distância = `4 - 2 = 2`
- `Volume = (min(70, 21) * 2 = 21 * 2 = 42)`
4. **Com `10` (índice 5):**
- Distância = `5 - 2 = 3`
- `Volume = (min(70, 10) * 3 = 10 * 3 = 30)`
5. **Com `2` (índice 6):**
- Distância = `6 - 2 = 4`
- `Volume = (min(70, 2) * 4 = 2 * 4 = 8)`
---
### 2. **Análise da Melhor Combinação**
Agora vamos considerar a combinação que gera o maior volume:
- A altura `15` (índice 1) combinada com a altura `21` (índice 4) tem:
- Distância = `4 - 1 = 3`
- `Volume = (min(15, 21) * 3 = 15 * 3 = 45)`
Embora `70` seja muito maior, ela não contribui para o maior volume porque:
1. Quando combinada com linhas próximas, a distância é curta, reduzindo o volume.
2. Quando combinada com linhas mais distantes, as alturas dessas outras linhas são muito pequenas, limitando o volume.
---
### Resumo da Afirmação
Mesmo que uma linha tenha uma altura muito grande (como `70`), ela **não garante o maior volume**. Isso ocorre porque:
- O volume é limitado pela **menor das duas alturas** escolhidas.
- O volume também depende da **distância entre as linhas**, que pode ser maior ao escolher outras combinações.
Portanto, é mais eficaz priorizar combinações que equilibrem **altura** e **distância**, mesmo que uma das alturas seja menor. Essa é a razão pela qual a altura `70` não contribui para o maior volume no exemplo dado.
---
### Conclusão
Os resultados apresentados para cada entrada correspondem ao esperado. A lógica de mover os ponteiros em direção ao centro permite otimizar a busca pelo maior volume de forma eficiente, garantindo que todos os casos sejam tratados corretamente.
---
### Hashtags
#ContainerWithMostWater, #Harbour, #TLPP, #Algorithms, #ProblemSolving, #DataStructures, #CodingChallenge, #LeetCode, #ProgrammingLogic, #EfficiencyInCode, #AlgorithmOptimization, #HarbourProgramming, #TLPPProgramming
(fig.: 1)
(fig.: 2)
Comentários
Postar um comentário