LeetCode_11: Container With Most Water

# 引言

题目链接：https://leetcode.com/problems/container-with-most-water/description/

# 题目大意

给定n个非负整数a1,a2,...,an, 其中每个代表一个点坐标(i,ai), 通过每个点做x轴的垂直线, 最后取任意两条线, 使得两条线与x轴所构成的容器能装最多的水。

Note: You may not slant the container and n is at least 2.(即水的面积不是容器的面积, 而是最大矩形的面积, 并且一定有解)

• Example

Input: [1,8,6,2,5,4,8,3,7]
Output: 49

# 题解

解题思路：

按照常识(木桶原理), 两条线段构成的容器有效高度由较短的一边确定, 整个容器的面积由坐标点index的差值和有效高度共同确定.

采取如下方式, 首先确定一个条件的最优值, 通过不断调优另一个条件值同时联动调整当前条件的值并跟踪最大值即可

即开始选择最大index差值, 即数字序列第一个和最后一个(这里用l,r表示)；然后考察容器有效高度.若height[l] > height[r], 那么舍弃r, 取r前一个考察, 否则取l后一个考察, 整个过程计算容器有效容积area=min(height[right],height[left])∗(right−left), 并不断维护即可

# 复杂度

时间复杂度 O(n)

空间复杂度 O(1)

# AC代码

c++版本

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

go版本

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

func maxArea(height []int) int {
	l, r := 0, len(height)-1
	var maxn int
	for l < r {
		maxn = max(maxn, min(height[l], height[r])*(r-l))
		if height[l] < height[r] {
			l++
		} else {
			r--
		}
	}
	return maxn
}