leetcode.com-problemset-all-011 - Container With Most Water
- 3 mins题目描述
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. 
The above vertical lines are represented by array [1,8,6,2,5,4,8,3,7]. In this case, the max area of water (blue section) the container can contain is 49.
难易程度
Easy- Medium
Hard
Example:
Input: [1,8,6,2,5,4,8,3,7]
Output: 49
PHP实现
方法一
自己没想到好的方法，用的是2个for循环实现的，就不在此丢脸了。
其他方法
// 36ms
class Solution {
/**
* @param Integer[] $height
* @return Integer
*/
function maxArea($height) {
$i = 0;
$j = count($height) - 1;
$maxArea = 0;
while ($i < $j) {
$width = $j - $i;
$length = min($height[$i], $height[$j]);
$area = $width * $length;
$maxArea = max($area, $maxArea);
if ($height[$i] > $height[$j]) {
$j--;
} else {
$i++;
}
}
return $maxArea;
}
}
Go实现
方法一
//12ms
// 对PHP例子中实现思路进行了go的重写
/**********************************************
** @Des: 11 - main
** @Author: zhanglingyu
** @Date: 2019-04-09 13:33
** @Last Modified time: 2019-04-09 13:33
***********************************************/
package main
import "fmt"
func main() {
height := []int{1,8,6,2,5,4,8,3,7}
fmt.Println(maxArea(height))
}
func maxArea(height []int) int {
i, j, maxArea := 0, len(height)-1, 0
for i < j {
width := j - i
length := min(height[i], height[j])
area := length * width
maxArea = max(area, maxArea)
if height[i] > height[j] {
j--
} else {
i++
}
}
return maxArea
}
func max(v1 int, v2 int) int {
if v1 > v2 {
return v1
}
return v2
}
func min(v1 int, v2 int) int {
if v1 > v2 {
return v2
}
return v1
}
其他方法
无
PS
- 1.
方法一一般是自己实现的方法，其他方式是在discuss中查找的更为优秀的方法，用作学习和借鉴。 - 2.由于本人水平有限，文章在表述和代码方面如有不妥之处，欢迎批评指正。