盛最多水的容器

LeetCode 11 · Medium · 1 min · 榎aaaa

如果直接用两个for循环遍历所有容积情况，时间复杂度是O(n^2)，会超时…..

所有需要使用正确的算法

那么这题使用的就是双指针的方法。

首先分析思路：虽然说是双指针，但实际上使用的是两个索引的方法–定义left=0（最左边），right=数组大小-1（最右边），然后计算出初始的容积大小

我们发现，移动长板（向里走，也就是将索引向里挪一位）会使水槽的宽度会变窄，即使移动过后得到的板子是更长的板子，容积仍然会变小，更短的板子同理（短板效应）；但是如果移动的是短板，假如下一块板子是更长的，那么就有可能会使容积变大（e.g.第一块板子长为1，最后一块板子长为7，一共九块板子，那么此时容积就是（1x8）=8，接下俩移动短板，第二块板子长为8，此时容积为（7x7）=49，容积变大了）

所以，只需要找到两块板子中更短的那块，固定住长板，只移动短板就行

 1
 2int maxArea(vector<int>& height)
 3
 4    {
 5
 6        int left = 0, right = static_cast<int>(height.size()) - 1;
 7
 8        int volumn = std::min(height[left],height[right]) * right;
 9
10        while(left < right)
11
12        {
13
14            if(height[left] < height[right])
15
16            {
17
18                left++;
19
20            }
21
22            else
23
24            {
25
26                right--;
27
28            }
29
30            volumn = std::max(volumn, (std::min(height[left],height[right]) * (right - left)));
31
32        }
33
34        return volumn;
35
36    }