LeetCode——11. 盛最多水的容器

    科技2024-04-23  64

    题目描述:

    解题思路:

    这道题题意说的很清楚,找到能容纳水最大的容积,直接两层for循环,更新最大值,这种方法思路很明确,但是内存和时间都很差,显然还有其他方法可以优化。 可以利用双指针,定义两段的柱子,然后根据大小来判断是左边指针移动还是右边指针移动。当左边小于右边的时候,移动左边指针,新的容积一定不会超过右边的,因为总要受到最小的柱子的限制,所有我们要优先更新小的柱子的指针。 参考代码:

    //暴力 public int maxArea(int[] height) { int max=0; for (int i = 0; i < height.length; i++) { for (int j = i+1; j <height.length ; j++) { int sq=(j-i)*Math.min(height[i],height[j]); max=Math.max(sq,max); } } return max; } //双指针 public int maxArea2(int[] height){ int l=0; int n=height.length; int r=n-1; int max=0; int sq; while (l<r){ sq=(r-l)*Math.min(height[l],height[r]); max=Math.max(max,sq); if(height[l]<height[r]) l++; else r--; } return max; }
    Processed: 0.031, SQL: 12