LeetCode刷题（C++）——Container With Most Water

ゞ浴缸里的玫瑰 2022-06-16 03:36 128阅读 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.

思路分析：本题的意思是对于一个数组\[1,3,2,5,6\]，在坐标系上显示如下，目的是要寻找两条垂直线与x轴组成的容器之间的最大面积，感觉类似于木桶效应。下图中最大的面积是3和6之间组成的区域。

![Center][]

**解法1：**暴力解法，时间复杂度为O(n^2)，通不过，稍微改进一下也是能够通过的。

class Solution {
    public:
        int maxArea(vector<int>& height) {
            if (height.size() < 2)
    			return 0;
    		int maxarea = 0;
    		for (int i = 0; i < height.size();++i)
    		{
    			if (height[i] != 0)
    			{
    				for (int j = i + (maxarea / height[i]);j < height.size();++j)           //如果是直接暴力解法 j=i+1;会超时
    				{
    					int len = j - i;
    					int wid = (height[i] > height[j]) ? height[j] : height[i];
    					int area = len*wid;
    					if (area > maxarea)
    						maxarea = area;
    				}
    			}
    		}
    		return maxarea;
        }
    };

**解法2：** 时间复杂度为O(n)

设置两个指针i和j，分别指向数组的两头，当a\[i\]>a\[j\]时，j往前移动，否则i往后移动，同时之前最大的面积比较。

class Solution {
    public:
        int maxArea(vector<int>& height) {
            if (height.size() < 2)
    			return 0;
    		int maxarea = 0;
    		int i = 0, j = height.size() - 1;
    		while (i < j)
    		{
    			maxarea = max(maxarea, min(height[i], height[j])*(j - i));
    			if (height[i] < height[j])
    				++i;
    			else
    				--j;
    		}
    		return maxarea;
        }
    };

[Center]: /images/20220616/4dc46ca067f748378307654ba9feb6cd.png