给定一个长度为 n 的整数数组 height 。有 n 条垂线,第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。

找出其中的两条线,使得它们与 x 轴共同构成的容器可以容纳最多的水。

返回容器可以储存的最大水量。

说明:你不能倾斜容器。

示例 1:

输入:[1,8,6,2,5,4,8,3,7]
输出:49 
解释:图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下,容器能够容纳水(表示为蓝色部分)的最大值为 49。

示例 2:

输入:height = [1,1]
输出:1

提示:

  • n == height.length
  • 2 <= n <= 10^5
  • 0 <= height[i] <= 10^4

分析:用两个指针分别指向容器的第一根线和最后一根线,而容器能够容纳的水量取决于两条线中较短的那条线,因此想让容器的盛水量增加,必须要改变较短的那条线。当两个指针不重合时,每次计算当前的盛水量,再移动指向较短的线的指针,直到指针重合为止。

int maxArea(int* height, int heightSize) {
    int l=0,r=heightSize-1,ans=fmin(height[r],height[l])*(r-l);
    printf("ans=%d\n",ans);
    while(l<r)
    {
        if(height[r]<height[l])r--;
        else l++;
        ans=fmax(ans,fmin(height[r],height[l])*(r-l));
    }
    return ans;
}

Logo

码道开发者社区,聚焦华为云码道 CodeArts 代码智能体,沉淀 Agent、Skill、鸿蒙开发实战内容,供开发者查阅资料、交流技术、分享工程实践

更多推荐