---
# System prepended metadata

title: 0011. Container With Most Water
tags: [Leetcode, 双指针]

---

###### tags: `Leetcode` `双指针`
# 0011. Container With Most Water
Link: https://leetcode.com/problems/container-with-most-water/
## 思路
由于暴力解法是loop套loop的形式，复杂度为n平方，因此为了省时间，要想一个只需要遍历一遍的方法。
这一题是求最大面积，不变的是每次移动一个格子，变的是长度，而长度取决于两根边里面最短的那个，因此我们可以每次把最短的那根替换掉。
## Code
```
class Solution {
public:
    int maxArea(vector<int>& height) {
        int max_area = 0;
        int l = 0;
        int r = height.size()-1;
        while(l<r){
            max_area = max(max_area, (r-l)*min(height[r], height[l]));
            if(height[r]>height[l]){
                l++;
            }
            else{
                r--;
            }
        }
        return max_area;
    }
};
```
## Notes
1.用```a = max(a,b)```代替```if(a>b){a = b}```，尤其是在a或b在算式的情况下
2.一开始我的解法是这样的（暴力硬解）
```
class Solution {
public:
    int maxArea(vector<int>& height) {
        int max_area = 0;
        for(int i = 0; i < height.size(); i++){
            for(int j = i+1; j < height.size();j++){
                max_area = max(max_area,(j-i)*min(height[i],height[j]));
            }
        }
        return max_area;
    }
};
```
和解答里面的第一个解法是一样的，不过解答里面用的是JAVA，但是用C++写的话就会超时，这部分其实是不太理解的


## Java
```
class Solution {
    public int maxArea(int[] height) {

        int tempArea, tempHeight;
        int max = 0;
        int i = 0, j = height.length-1;
        while(i < j){
            tempHeight = height[i]<height[j] ? height[i] : height[j];
            tempArea = tempHeight * (j-i);
            if (tempArea > max) max = tempArea;
            if (height[i] > height[j]) --j;
            else ++i;
        }
        return max;
    }
}
```
### 过程
分别定义两个序号$x_1$和$x_2$，初始指向数组的头和尾，然后$x_1$可以向尾移动，$x_2$可以向头移动。因为$x_1$或$x_2$的移动会导致盛水的底减小，因此只有让$x_1$和$x_2$所对应的数组值更小的那个移动才有可能使得盛水变多。这样时间复杂度是$O(n)$。