11. Container With Most Water（求能装最多水的容器）

╰半夏微凉° 2022-06-09 14:23 118阅读 0赞

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.

Note: You may not slant the container and n is at least 2.

题目大意：给定一个长度为n的数组a\[n\]，在二维空间形成n个点（x=i，y=a\[i\]），找出两个点，使得这两个点到x轴的垂线与x轴构成一个容器，容器的容积最大。容器不能倾斜，而且n>=2。

解题思路：

对于n个点，要求得最大的容积，可以分两种情况：

1. 宽度为n，高度为a\[0\]和a\[n-1\]中较小的值;

2. 舍弃掉（i，a\[i\]）这个点，其中i = a\[0\]和a\[n-1\]中较小的值的下标，然后在剩下的n-1个点中找得两个点，构成容积最大的容器。

直到宽度为1的时候，直接去高度为a\[i\]。

递归代码：（leetcode测试用例太大，报了StackOverFlow）

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

循环代码：（10ms，beats 52.47%）

class Solution {
        public int maxArea(int[] height) {
    		int len = height.length;
    		int[] area = new int[len];
    		int left = 0, right = len - 1;
    		while (right > left) {
    			area[right - left - 1] = (right - left) * Math.min(height[left], height[right]);
    			if (height[left] > height[right]) {
    				right--;
    			} else {
    				left++;
    			}
    		}
    		int max = 0;
    		for (int i = 0; i < len; i++) {
    			if (area[i] > max) {
    				max = area[i];
    			}
    		}
    		return max;
    	}
    }