首页 > 基础算法 > 贪心 > 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
            
        

  1. 迪士尼或者说整个好莱坞老是干这种吃力不讨好的东西,上一部冰雪奇缘算是米老鼠自家最拿手的公主电影,几十年经验在那里自然做的游刃有余,所以在日本掀起了高票房的狂潮,结果自以为做一部有日本元素的动画电影一定能超过frozen的票房,结果压根就摸不准东亚人的兴趣

  2. 迪士尼或者说整个好莱坞老是干这种吃力不讨好的东西,上一部冰雪奇缘算是米老鼠自家最拿手的公主电影,几十年经验在那里自然做的游刃有余,所以在日本掀起了高票房的狂潮,结果自以为做一部有日本元素的动画电影一定能超过frozen的票房,结果压根就摸不准东亚人的兴趣

  3. 迪士尼或者说整个好莱坞老是干这种吃力不讨好的东西,上一部冰雪奇缘算是米老鼠自家最拿手的公主电影,几十年经验在那里自然做的游刃有余,所以在日本掀起了高票房的狂潮,结果自以为做一部有日本元素的动画电影一定能超过frozen的票房,结果压根就摸不准东亚人的兴趣

  4. 迪士尼或者说整个好莱坞老是干这种吃力不讨好的东西,上一部冰雪奇缘算是米老鼠自家最拿手的公主电影,几十年经验在那里自然做的游刃有余,所以在日本掀起了高票房的狂潮,结果自以为做一部有日本元素的动画电影一定能超过frozen的票房,结果压根就摸不准东亚人的兴趣

  5. 迪士尼或者说整个好莱坞老是干这种吃力不讨好的东西,上一部冰雪奇缘算是米老鼠自家最拿手的公主电影,几十年经验在那里自然做的游刃有余,所以在日本掀起了高票房的狂潮,结果自以为做一部有日本元素的动画电影一定能超过frozen的票房,结果压根就摸不准东亚人的兴趣

  6. 迪士尼或者说整个好莱坞老是干这种吃力不讨好的东西,上一部冰雪奇缘算是米老鼠自家最拿手的公主电影,几十年经验在那里自然做的游刃有余,所以在日本掀起了高票房的狂潮,结果自以为做一部有日本元素的动画电影一定能超过frozen的票房,结果压根就摸不准东亚人的兴趣

  7. 迪士尼或者说整个好莱坞老是干这种吃力不讨好的东西,上一部冰雪奇缘算是米老鼠自家最拿手的公主电影,几十年经验在那里自然做的游刃有余,所以在日本掀起了高票房的狂潮,结果自以为做一部有日本元素的动画电影一定能超过frozen的票房,结果压根就摸不准东亚人的兴趣

  8. 迪士尼或者说整个好莱坞老是干这种吃力不讨好的东西,上一部冰雪奇缘算是米老鼠自家最拿手的公主电影,几十年经验在那里自然做的游刃有余,所以在日本掀起了高票房的狂潮,结果自以为做一部有日本元素的动画电影一定能超过frozen的票房,结果压根就摸不准东亚人的兴趣

  9. 迪士尼或者说整个好莱坞老是干这种吃力不讨好的东西,上一部冰雪奇缘算是米老鼠自家最拿手的公主电影,几十年经验在那里自然做的游刃有余,所以在日本掀起了高票房的狂潮,结果自以为做一部有日本元素的动画电影一定能超过frozen的票房,结果压根就摸不准东亚人的兴趣

  10. 迪士尼或者说整个好莱坞老是干这种吃力不讨好的东西,上一部冰雪奇缘算是米老鼠自家最拿手的公主电影,几十年经验在那里自然做的游刃有余,所以在日本掀起了高票房的狂潮,结果自以为做一部有日本元素的动画电影一定能超过frozen的票房,结果压根就摸不准东亚人的兴趣

  11. 迪士尼或者说整个好莱坞老是干这种吃力不讨好的东西,上一部冰雪奇缘算是米老鼠自家最拿手的公主电影,几十年经验在那里自然做的游刃有余,所以在日本掀起了高票房的狂潮,结果自以为做一部有日本元素的动画电影一定能超过frozen的票房,结果压根就摸不准东亚人的兴趣