[讨论leetcode 11]最多水的容器Container With Most Water

我自己只想到O(n2) solution, 没有想到更高效的，看了下别人的答案，甚是巧妙。自己也实现了一下，就是不断更新矩形start，end的值.附上ac code

1. class Solution {
   
2. public:
   
3.     int maxArea(vector<int>& height) {
   
4.         int start = 0, end = height.size() - 1;
   
5.         int maxArea = 0;
   
6.         while(start < end)
   
7.         {
   
8.             int h = min(height[start], height[end]);
   
9.             int cur = (end - start)*h;
   
10.             maxArea = max(maxArea, cur);
    
11.             if(h == height[start])start++;
    
12.             else end--;
    
13.         }
    
14.         return maxArea;
    
15.     }
    
16. };

复制代码

我的疑问在于：它没有特殊讨论height[start] == height[end]情况下，start还是end move. 而且start或end move下来的结果肯定是不一样的而且后续的矩形也会跟着不同，但是这版code还是ac了，没想通为什么。求大神提点！！

你这样考虑：

现在H=height[start]==height[end]，他的跨度是end-start。
对于之后的，不管是先移动start还是end，下一个的高度肯定小于等于当前的高度H，但是宽度一定比当前的宽度小，所以移动谁都不影响结果。

waterfish 发表于 2019-6-4 04:37
你这样考虑：

现在H=height[start]==height[end]，他的跨度是end-start。

1.宽度一定比之前的宽度小，没有问题；
2.移动之后的高度height[++start]或者height[--end]是有可能比之前大的，但是此时无论++start或者--end的面积都一定比之前小，没有问题；但是再进一步就不一定了，不知道我有没有说清楚

plugin1689 发表于 2019-6-4 11:46
1.宽度一定比之前的宽度小，没有问题；
2.移动之后的高度height[++start]或者height[--end]是有可能比 ...

对，没错，但是height[++start]与任何的height[start+2~end]或者height[--end]与任何的height[start~end-2]的高度一定小于等于height[++start]和height[--end]，也就是这两个点start+1和end-1永远都不会被用作最优解了。所以先移动谁都没关系。

waterfish 发表于 2019-6-4 13:01
对，没错，但是height[++start]与任何的height[start+2~end]或者height[--end]与任何的height[start~end- ...

懂你的意思了，无论++start还是--end，最优解都不会出现在这两个点上，也就是说最优解存在于是开区间(start, end), 所以无论是[start, end), 还是(start, end] 都是没有影响的。牛逼啊！！感谢大佬！！