leetcode 11号问题

Question

AKA, the general idea to find some max is to go through all cases where max value can possibly occur and keep updating the max value. The efficiency of the scan depends on the size of cases you plan to scan.
To increase efficiency, all we need to do is to find a smart way of scan to cut off the useless cases and meanwhile 100% guarantee the max value can be reached through the rest of cases.

In this problem, the smart scan way is to set two pointers initialized at both ends of the array. Every time move the smaller value pointer to inner array. Then after the two pointers meet, all possible max cases have been scanned and the max situation is 100% reached somewhere in the scan. Following is a brief prove of this.

Given a1,a2,a3.....an as input array. Lets assume a10 and a20 are the max area situation. We need to prove that a10 can be reached by left pointer and during the time left pointer stays at a10, a20 can be reached by right pointer. That is to say, the core problem is to prove: when left pointer is at a10 and right pointer is at a21, the next move must be right pointer to a20.

Since we are always moving the pointer with the smaller value, i.e. if a10 > a21, we should move pointer at a21 to a20, as we hope. Why a10 >a21? Because if a21>a10, then area of a10 and a20 must be less than area of a10 and a21. Because the area of a10 and a21 is at least height[a10] * (21-10) while the area of a10 and a20 is at most height[a10] * (20-10). So there is a contradiction of assumption a10 and a20 has the max area. So, a10 must be greater than a21, then next move a21 has to be move to a20. The max cases must be reached.

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

老师帮忙看看，这个是我在Leecode上看大的11号问题的解答，while语句里面maxArea倒是很好理解；

            if (height[left] < height[right])
		left++;	
		else
		right--;

对于这个片段我不是太理解他的思路，由于英文水平有限上面的翻译借助了谷歌翻译，翻译出来的描述总感觉怪怪的，还望老师说明一下这个代码片段的含义！

在此谢过老师了！

Answer 1

liuyubobobo 2017-08-02 23:09:15

相信题意你已经理解了。整体解题思路大意是这样的：首先用整个数组的最左侧和最右侧作为容器的边界，然后去不断寻找有没有容积更大的容器。寻找方式是每次把左右边界里更矮的那一边向“里”推一步。也就是如果左边界更矮，就试试用左边界右边的那个高度当新的左边界；如果右边界更矮，就试试用右边界左边的那个高度当新的右边界。这就是下面这个代码片段的意思

if (height[left] < height[right])
    left++;
else
    right--;

直到左右边界对撞，也就是容器的底边为0了，搜索结束。所以我把这个问题放在了“对撞指针”这一小节

这个算法为什么成立呢，在这里不去严谨证明了。不过我们可以形象的理解一下：初始的情况是底边最长的情况，在这样的情况下，如果存在容积更大的容器，底边肯定会缩小。此时唯一的方法就是增加高度。我们每次都尝试舍弃两边最短的那个高度，来看新的高度能不能构建出容积更大的容器出来。

• 提问者 22不小了 #1

  非常感谢老师您的回答，我当时的疑惑就是当左右边界向中间靠拢的时候，宽度必然缩短、而
  if (height[left] < height[right])
      left++;
  else
      right--;
  如何在遍历缩小宽度时，去寻找更高的高度。并保证不会遗漏掉可能的情况。看了老师最后一段解说，我似乎感觉是明白了。但是这个数学上是如何证明的，我还是不得而知。不过也没有关系，继续跟着课程往前走，给自己留下一个疑问，以后抽空去查看这背后的数学证明。最后还是要再次感老师您，辛苦老师您了！

Answer 2

liuyubobobo 2017-08-04 13:23:43

我试着严谨的证明一下。这个问题本质上也是在使用贪心算法。贪心算法的证明通常都是假设不使用这个贪心过程，找到矛盾，所谓反证法。（计算机领域的证明，主要使用数学归纳法和反证法两种方式）

现在，我们假设，存在一组数据，如果我们使用这个算法，我们找到的不是它的容器的最大值。

换句话说，对于这组数据来说，假设容器的最大值在[resL, resR]这个左右位置。那么至少存在一步，我们不遵守这个算法才能找到最优解。假设这一步是搜索到[L0, R0]的时候。设L0的右端为L1，R0的左端为R1，就是 L0, L1, ..., R1, R0的形状。又假设有L0>R0（L0<R0的情况是对称的）。此时，我们必须通过[L1, R0]才能找到这个最优解（也就是把两端大的那一段往里推），而不是通过[L0, R1]才能找到这个最优解。

设想一下，在什么情况下，我们才必须通过[L1,R0]才能找到这个最优解[resL, resR]呢？只有一种情况，就是R0 == resR。否则，如果resR < R0的话，也就是resR <= R1，我们通过[L0,R1]一样能找到这个最优解，与我们的假设：必须通过[L1, R0]才能找到这个最优解 矛盾。

换句话说，此时这个最优解在[L1, resR]的这个区间里，且存在resL >= L1, L0 > resR。

这时，假设L1和resR之间的底边长度为a的话，这个解的容积S一定满足 S <= k*resR。这是因为，由于我们的右边缘已经固定，整个容器的高度不可能超过resR，而底边也不可能超过k了。

但是，此时我们根据这些条件看[L0, resR]这个区间，就会发现这个区间的容积为(k+1)*resR，是大于S的。换句话说，此时的解一定是[L0, resR]，这个解是不在[L1,resR]这个区间里的。产生了矛盾，所以我们的假设不成立。

所以，我们的假设“存在一组数据，如果我们使用这个算法，我们找到的不是它的容器的最大值。”错误。使用这种算法，可以找到任何一组数据在这个问题下的容器最大值。

• 提问者 22不小了 #1

  谢谢老师您的回答！这么一说我就明白了。在此感谢老师！