力扣—盛水最大的容器—双指针

文章目录

• • 题目解析
  • 解题思路
  • 代码实现

题目解析

解题思路

利用单调性控制其中一个变量，使用双指针控制另一个变量。
我们知道S1(面积)=h(高度)*w(宽度)。由于高度的大小是随机的不可控，所以我们可以尝试控制宽度，定义变量
left和right分别指向数组第一个元素和最后一个元素，此时可以得到S1=(right-left)*fmin(height[left],height[right])
当宽度向中间收缩时成不断递减的趋势，所以要得到最大的S必须要求高度尽可能的大，此时就需要舍弃
(height[left],height[right])中较小的那个高度，得到新的S2和S1比较取较大值。

代码实现

C语言实现

int maxArea(int* height, int heightSize) 
{
    int left=0;
    int sum=0;
    int right=heightSize-1;
    int max=0;
    while(left<right)
    {
        int sum=(right-left)*fmin(height[left],height[right]);
        if(height[left]<height[right])
        {
            left++;
        }
        else
        {
            right--;
        }
        max=fmax(sum,max);
    }
    return max;
}

Java实现

class Solution {
    public int maxArea(int[] height) 
    {
      int left=0;
      int right=height.length-1;
      int ret=0;
      while(left<right)
      {
        int v=(right-left)*Math.min(height[left],height[right]);
        if(height[left]<height[right])
        {
            left++;
        }
        else
        {
            right--;
        }
       ret=Math.max(ret,v);
      }
      return ret;
    }
}

感谢您的阅读，欢迎留言评论。