首先我们设该容器的两边为左右两边界。
这道题中的:盛⽔最大容量 = 底 * 高 = 左右两边界距离 * 左右两边界的较短板。
这道题如果用暴力求解,是个人都能想到怎么做,遍历所有的情况即可。
有没有更好的办法呢?我是搜了资料了解的。我觉得一般人【有可能只是我的知识水平太低才有这样的看法】第一次做想不出来这种情况,我们只能通过这道题的更优的思想在日后做题中可以借鉴。
那么这道题的更优法是什么呢?
首先一个容器肯定是有两边界和底边组成的,这道题的核心就是我们要找到底边*高度的最大值。
我们先把最左和最右作为容器的边界记录此时的容量,然后把左右边界的短板向相反方向移动,记录。继续移动短板知道左右指针相遇结束,取这些值的最大值作为结果。
怎么理解?
暴力求解是遍历所有的可能取最大值,这种做法其实就是依据给出的条件结合当下能利用的数据尽量的选择了一些尽可能大的值,取最大值作为结果。
为什么移动短板?
初识左右指针为最左和最右,此时我们移动其中一个,移动高的还是低的?只要移动一边,底肯定变小,如果还是移动高的一边,不仅底小了,高也小了,如果移动地的一边,虽然底小了,但是高大了,即若向内移动短板,下个水槽的面积可能增大 。若向内移动长板,下个水槽的面积一定变小。
他是如何保证舍去的值不是较大值呢?
向内移动短板(假设该短板的下标为x,此时右边界的下标为y),实际上是舍去了将x作为左边界到y-1的集合,即暴力求解是n边取2边的所有取值的集合,这个解法是每一步舍去不会作为较大值的集合。如何保证舍去的值不是较大值呢?即如何保证将x作为左边界到y-1的集合不是较大值?这些集合分别是【x, y-1】【x, y-2】… 【x, x+1】这些集合中所有取值的底边都比已经作为较大值的【x, y】的底边小,所有的高度都比已经作为较大值的【x, y】的高度小或者等于。为什么?假设这些集合中的某一个右边比x大,由于容器容量取决于短板,故高度取x;假设这些集合中的某一个右边比x小,由于容器容量取决于短板,故高度取这个右边;底边小且高度小于等于 ⇒ 舍去的都不是较大值,即舍去的可以放心舍去。
代码
class Solution
{
public:int maxArea(vector<int> &height){int left = 0, right = height.size() - 1, ret = 0;while (left < right){int volume = min(height[left], height[right]) * (right - left);ret = max(ret, volume);// 移动短板if (height[left] < height[right])left++;elseright--;}return ret;}
};