11. Container With Most Water

發表於 | 分類於

problem

從陣列中，找出最大積水量

solution

  • 兩個索引分別從左往右，從右往左，直到兩索引相等時跳出迴圈，尋找最大積水量
1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    int maxArea(vector<int>& height) {
        int n = height.size();
        int l = 0,r =n-1, ret = 0;
        while(l<r){
            ret = max(ret, (r-l)*min(height[l], height[r]));
            height[l] < height[r] ? ++l : --r;
        }
        return ret;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    int maxArea(vector<int>& height) {
        int res = 0, i = 0, j = height.size() - 1;
        while (i < j) {
            int h = min(height[i], height[j]);
            res = max(res, h * (j - i));
            while (i < j && h == height[i]) ++i;
            while (i < j && h == height[j]) --j;
        }
        return res;
    }
};

analysis

  • time complexity O(n)
  • space complexity O(1)