leetcode-11-Container-With-Most-Water

发表于   |  

描述

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.

img

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.

Example:

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

分析

容器的面积取决于最短的木板，通过左右两边的指针向中心移动就可以遍历所有情况。时间复杂度是 $O(n)$，空间复杂度是 $O(n)$ 。

解决方案1（Python）

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def maxArea(self, height: List[int]) -> int:
        left, right = 0, len(height) - 1
        result = 0
        while left < right:
            now = min(height[left], height[right])*(right-left)
            result = max(result, now)
            if height[left] <= height[right]:
                left += 1
            else:
                right -= 1
        return result

解决方案2(Java)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public int maxArea(int[] height) {
        int result = 0, l = 0, r = height.length - 1;
        while (l < r) {
            result = Math.max(result, Math.min(height[l], height[r]) * (r-l));
            if (height[l] < height[r]) {
                l++;
            } else {
                r--;
            }
        }
        return result;
    }
}

解决方案3(Javascript)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/**
 * @param {number[]} height
 * @return {number}
 */
var maxArea = function(height) {
    var result = 0;
    var l = 0;
    var r = height.length - 1;
    
    while (l <= r) {
        result = Math.max(result, Math.min(height[l], height[r]) * (r-l));
        if (height[l] < height[r]) {
            l++;
        } else {
            r--;
        }
    }
    return result;
};

解决方案4(Rust)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
pub struct Solution {}

impl Solution {
    pub fn max_area(height: Vec<i32>) -> i32 {
        let (mut l, mut r) = (0_usize, (height.len() - 1));
        let mut result: i32 = (r - l) as i32 * Solution::min(height[l], height[r]);
        let mut current: i32 = 0;
        while l < r {
            if height[l] < height[r] {
                l += 1;
            } else {
                r -= 1;
            }
            current = (r - l) as i32 * Solution::min(height[l], height[r]);
            if current > result {
                result = current
            }
        }
        result
    }

    #[inline(always)]
    fn min(i: i32, j: i32) -> i32 {
        if i > j {
            j
        } else {
            i
        }
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_leetcode_11() {
        assert_eq!(Solution::max_area(vec![1, 8, 6, 2, 5, 4, 8, 3, 7]), 49);
    }
}

相关问题

题目来源