盛最多水的容器

发布于 2020-07-19 09:27:25   阅读量 48  点赞 0  

原题地址:https://leetcode-cn.com/problems/container-with-most-water/

题目

 给你 n 个非负整数 a_1,a_2,...,a_n,每个数代表坐标中的一个点 (i,a_i) 。在坐标内画 n 条垂直线,垂直线 i 的两个端点分别为 (i,a_i)(i,0)。找出其中的两条线,使得它们与 x 轴共同构成的容器可以容纳最多的水。

说明:你不能倾斜容器,且 n 的值至少为 2。



示例:

输入:[1,8,6,2,5,4,8,3,7]
输出:49



解法

 类似于这种匹配问题,首先考虑用双指针法求解。首先设置首尾指针startend分别指向数组首尾,指针移动的规则为:每次选定围成水槽的两板高度中较短的板,向中间收窄一格

  • 由于容器的容积计算公式为 S(i,j) = min(h[i],h[j])*(j-i),在每一个状态下,向中间收窄都会导致水槽 底边宽度 - 1

  • 若移动短板,水槽的短板 min(h[i],h[j]) 有可能变大,因此水槽的容积有可能增大;而若移动长板,水槽的短板 min(h[i],h[j]) 只会不变或变小,下个水槽容积一定小于当前水槽容积。

 双指针法的核心在于在匹配问题中排除不可能为解(即题中的最大值)的情况,而使用上述算法消去的容积,都有 消去的容积 <当前容积S(i,j),即不可能成为最大容积的情况。

 虽然,指针移动的结果不一定向着目标(容积最大)逼近,但排除掉了不可能为解的情况,算法最终遍历的为可能解的集合,即,双指针法减小了可能解的集合,使得算法时间复杂度下降。



双指针

 双指针法适用于匹配问题如:《盛最多水的容器》(找出容积最大的两块板的组合)、《三数之和》(找出三数之和为 0 的组合)。

 双指针中首尾指针的移动趋势都是向中间移动,而双指针的核心在于找出首尾指针移动的准则(移动首指针还是尾指针)。判断标准取决于,移动哪个指针能够排除掉不可能的解,从而减小遍历的范围,此时指针的移动不一定能够使得问题朝着解的方向逼近。

 如在《盛最多水的容器》中,若移动较长板的指针,则容积只会变小或不变,不可能为最优解。故移动指向较短板的指针,不将较短板与其他边的组合纳入考虑范围,排除掉不可能作为最优解的其他情况。

 在《三数之和》中,要找出三数之和为 0 的情况。先将数组排序,同样根据三数之和的正负移动首尾指针,若和为正,则移动尾指针,使得和变小(若移动首指针,则和变大,结果不可能为0);和为负时亦然。目标同样为排除掉不可能为解的情况。



代码

int maxArea(vector<int> &height) {
    int start = 0;
    int end = height.size()-1;
    int maxVolume = 0;
    while (start<end){
        if(height[start]<height[end]){
            maxVolume = maxVolume>height[start]*(end-start)?maxVolume:height[start]*(end-start);
            start++;
        }else{
            maxVolume = maxVolume>height[end]*(end-start)?maxVolume:height[end]*(end-start);
            end--;
        }
    }
    return maxVolume;
}


Last Modified : 2020-07-20 15:52:18