网页直达:

https://leetcode.cn/problems/container-with-most-water

题目分析

1.其实高度就是"木桶效应"

2.暴力枚举:选两个高度算面积,找到最大值,但是超时.

3.双指针法:我们从两边开始向里面遍历,发现会有宽度和高度的变化

情况一:向里面遍历宽度w一定是减小的,假设此时的高度h不变.容积v变小

情况二:向里面遍历,宽度w和高度h都有变小.容积变小.

这些情况的枚举就可以去除了,其实就是部分枚举.

代码思路:

无详解:

class Solution {
public:
    int maxArea(vector<int>& height) {
        int right=height.size()-1;
        int left=0;;
        int curvm,maxv=0;
        while(right>left)
        {
            curvm=(right-left)*min(height[left],height[right]);
            maxv=max(maxv,curvm);
            if(height[right]<height[left])
            {
                right--;
            }
            else
            {
                left++;
            }
        }
        return maxv;
    }
};

详解和注释:

具体过程还是比较感性的,动态的分析画图也很有效.

知道容器的接口,熟练的使用,写代码更加简单.

class Solution {
public:
    int maxArea(vector<int>& height) {
        int right=height.size()-1;//定义左右指针指向
        int left=0;;
        int curvm,maxv=0;//当前枚举的面积,和最大面积
        while(right>left)//从两边向里面遍历
        {
            curvm=(right-left)*min(height[left],height[right]);//水桶效应,min的高*宽
            maxv=max(maxv,curvm);//更新最大值
            if(height[right]<height[left])// 移动指针：总是移动高度较小的一侧
            {
                right--;
            }
            else
            {
                left++;
            }
        }
        return maxv;
    }
};