11. 盛最多水的容器(LeetCode )——C语言
文章目录
暴力破解法——循环遍历所有可能的边界组合
int maxArea(int* height, int heightSize){
int max = 0;
for (int i = 0; i < heightSize; i++) {
for (int j = i + 1; j < heightSize; j++) {
int min = height[i] < height[j] ? height[i] : height[j];
if (min * (j - i) > max) {
max = min * (j - i);
}
}
}
return max;
}双指针法:
容器容量由min(height[i], height[j])*(j-i)决定。如果从较大的数移动指针(假设height[j]比较大),获得的容量值肯定小于移动前的容量值。因为j-i的值变小了,而min(height[i],height[j-1])的值取决于height[j-1]。如果 height[i] <= height[j-1] <= height[j],则min(height[i],height[j-1])的值为height[i],如果 height[j-1] < height[i],则min(height[i],height[j-1])的值小于height[i],即移动较大的数之后,min(height[i],height[j-1]) <= min(height[i], height[j]),而j-1-i < j - i,那么min(height[i], height[j - 1])*(j- 1 - i) < min(height[i], height[j])*(j - i)。因此,我们只要移动指向较小的数的指针即可,将每次求得的最大值与上一次的值进行比较,如果更大,则更新该值,否则继续移动指针,知道两个指针重合。
int maxArea(int* height, int heightSize){
int max = 0;
for (int i = 0, j = heightSize - 1; i < j; ) {
// 获取较小的数的下标
int min = height[i] <= height[j] ? i : j;
// 更新max
if (height[min] * (j - i) > max) {
max = height[min] * (j - i);
}
// 移动指针(指向较小的数的指针)
if (min == i) {
i++;
} else if (min == j) {
j--;
}
}
return max;
}
时间复杂度:O(n)
空间复杂度:O(1)

评论
登录后参与技术讨论,分享你的经验与见解。
登录 / 注册暂无评论