LeetCode: Container With Most Water

思路分析

还是利用经典的双端遍历思想,设i,j分别指向头尾。因为我们知道容量取决于短板,所以每次如果h[i] >= h[j],那么就应该尝试改进短板,即j--,否则就i++。在遍历的过程中注意记录一下每次的值是否大于最大值即可,终止条件是i < j

代码

class Solution {
public:
    int maxArea(vector<int> &height) {
        int res = 0;
        for ( int i = 0, j = height.size() - 1; i < j; ) {
            res = max(res, min(height[i], height[j]) * (j - i));
            if ( height[i] >= height[j] ) {
                j--;
            } else {
                i++;
            }
        }
        return res;
    }
};
comments powered by Disqus
Published:
2014-08-04
分类:
Tag:
DP15