JZTXT

11. 盛最多水的容器

发布时间 2023-04-27 10:35:57作者: 无形深空

11. 盛最多水的容器
看了下数据量, 暴力法肯定是性不同
使用双指针, 关键在于首先选取两端, 由于短板效应, 移动长板后, 容量肯定是不会增加的; 故每次都移动短板

class Solution {
public:
    int maxArea(vector<int>& h) {
        //max(h[i],h[j])*(j-i) 
        //两根指针, 分别指向第首位两条线
        int left = 0;
        int right = h.size()-1;
        //计算某两根线间可以容纳的水 认为此时就是最多
        int vol = (right-left)*min(h[left],h[right]);
        while(left != right)
        {
            //移动较短的那根才有可能更多
            (h[left]<h[right])?left++:right--;
            //如果水更多,就更新容量
            int vol_new = (right-left)*min(h[left],h[right]);
            vol = (vol_new>vol)?vol_new:vol;
        }
        return vol;
    }
};

转一个优雅的代码, 虽然运行速度和消耗内存都差不多

class Solution {
public:
    int maxArea(vector<int>& height) {
        int i = 0, j = height.size() - 1, res = 0;
        while(i < j) {
            res = height[i] < height[j] ? 
                max(res, (j - i) * height[i++]): 
                max(res, (j - i) * height[j--]); 
        }
        return res;
    }
};

作者：jyd
链接：https://leetcode.cn/problems/container-with-most-water/solution/container-with-most-water-shuang-zhi-zhen-fa-yi-do/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。