leetcode-11 容器装水最多

xiaoxiao2023-03-27  36

链接 

测试用例:

Input: [1,8,6,2,5,4,8,3,7] Output: 49

int maxArea(vector<int>& height) { int maxWater = 0; int i = 0, j = height.size() - 1; while (i < j) { int m=min(height[i], height[j]); maxWater = max(maxWater,(j - i)*m); while (height[i] <= m&&i<j) { i++; }//一定要强调i<j不然的话会溢出 while (height[j] <= m&&i<j) { j--; } } return maxWater; }

解释:Start by evaluating the widest container, using the first and the last line. All other possible containers are less wide, so to hold more water, they need to be higher. Thus, after evaluating that widest container, skip lines at both ends that don't support a higher height. Then evaluate that new container we arrived at. Repeat until there are no more possible containers left.

 

转载请注明原文地址: https://www.6miu.com/read-4988253.html

最新回复(0)