首页 > 基础算法 > 贪心 > LeetCode-Container With Most Water[贪心]
2014
11-19

LeetCode-Container With Most Water[贪心]

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.

标签: Array Two Pointers
分析

每个容器的面积,取决于最短的木板。

代码1

// LeetCode, Container With Most Water
// 时间复杂度O(n),空间复杂度O(1)
class Solution {
public:
    int maxArea(vector<int> &height) {
        int start = 0;
        int end = height.size() - 1;
        int result = INT_MIN;
        while (start < end) {
            int area = min(height[end], height[start]) * (end - start);
            result = max(result, area);
            if (height[start] <= height[end]) {
                start++;
            } else {
                end--;
            }
        }
        return result;
    }
};

Java代码:

class Solution:
    # @return an integer
    def maxArea(self, height):
        i=0
        j=len(height)-1
        res = 0
        while i < j :
            res = max(res, min(height[i],height[j]) * (j-i))
            if height[i] < height[j]:
                i += 1
            else:
                j -= 1
        return res