LeetCode: Container With Most Water [Java]

Myth丶恋晨 2022-08-06 12:23 120阅读 0赞

Description: Given n non-negative integers a1, a2, ..., an, where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of line i is at (i,ai) and (i, 0). Find two lines, which together with x-axis forms a container, such that the container contains the most water.

直观上，该题目可以通过遍历所有的两条线i和j组合得到最大值，时间复杂度为O(n^2)，代码如下所示：

public int maxArea(int[] height) {
          int result = 0;
    		int len = height.length;
            for(int i=0; i<len; i++) {
            	for(int j=0; j<len; j++) {
            		int min = height[i]<height[j] ? height[i] : height[j];
            		int product = (j - i) * min;
           			result = result>product ? result : product;
            	}
            }
            return result;
        }

很不幸，该程序提示超时。

经过分析题目需求发现：

![Center][]

**1、在两条线距离一定的情况下，容器盛水的多少由高度较短的那条边确定**

例如上图中，对于线i和线j，由于i对应的高度比j对应的高度低，所以线i和线j之间的盛水量为：water = a\[i\]\*(j-i)。

**2、找到两条线i和j中高度较小的线为i，那么这两条线中任何一条线与线i构成的容器的盛水量都会小于线i和线j对应的盛水量**

在上图中，因为线i的高度a\[i\]比线j的高度a\[j\]小，对于线i和线j之间所有的线k，其与线i构成的容器盛水量肯定小于线i与线j对应的容器的盛水量。

基于上面两条，我们发现一个只需要遍历数组一遍的算法，算法思想如下：

1.  **从数组的首尾同时遍历这个数组，假设我们有两个“指针”（java中没有指针，这里为了说明的方便）：首指针p1和尾指针p2；**
2.  **记录p1和p2对应的线构成的容器的盛水量Volume；**
3.  **比较p1和p2对应的线高度，如果p1对应的线的高度小于p2对应的高度，那么我们将p1向后移动一步，反之，我们将p2向前移动一步；**
4.  **比较新得到的盛水量与Volume的大小，并保存较大的值。**

实现代码如下所示：

public int maxArea(int[] height) {
    		int result = 0;
    		int i = 0;
    		int j = height.length - 1;
    		while(i < j) {
    			if(height[j] <= height[i]) {
    				int area = height[j] * (j - i);
    				result = result>area ? result : area;
    				j--;
    			} else {
    				int area = height[i] * (j - i);
    				result = result>area ? result : area;
    				i++;
    			}
    		}
    		return result;
    	}

再次提交， **程序AC了** ，很明显 时间复杂度为O(n) 。

但是我通过查看程序运行结果，即提交后的"detail"，发现我的程序运行时间比大部分算法都慢（运行时间为335ms），既然时间复杂度已经降到O(n)了，也就是说肯定不能从量级上面优化算法了，那么可不可以减少程序的处理次数呢？

因为通过上面两条我们发现，如果两条线i和j（i<j），且a\[i\]<a\[j\]，那么就不存在i<k<j，满足线i和线k构成的容器盛水量多于线i和线j了，因此我们需要将算法中指向线i对应的“指针”p1向后移动一步，但是我们**没有考虑到移动一步后对应的线(i+1)与线i的高度，即a\[i+1\]与a\[i\]的关系，如果****a\[i+1\]<=a\[i\]，那么很明显，线(i+1)与线j构成的容器的盛水量肯定小于线i与线j构成容器对应的盛水量，也就是说只有当****a\[i+1\]>a\[i\]时，我们才需要计算新的盛水量**，**这样我们可以在程序中添加两个while循环**。那么程序修改如下：

<span style="color:#333333;">public int maxArea(int[] height) {
    		int result = 0;
    		int i = 0;
    		int j = height.length - 1;
    		while(i < j) {
    			if(height[j] <= height[i]) {
    				int area = height[j] * (j - i);
    				result = result>area ? result : area;
    				j--;
    				while(height[j] < height[j+1]) 
    				<span style="white-space:pre">	</span>j--;
    			} else {
    				int area = height[i] * (j - i);
    				result = result>area ? result : area;
    				i++;
    				while(height[i] < height[i-1]) 
    					i++;
    			}
    		}
    		return result;
    	}</span>

第三次提交，**程序运行时间降到了227ms** 。

[Center]: /images/20220806/6d88aaa86ed746349c2477711c97b21a.png