关关的刷题日记93 – Leetcode 11. Container With Most Water

关关的刷题日记93 – 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.

题目的意思是给定n个非负整数a1, a2, ..., an，每个数代表坐标点(i, ai)。在坐标上画了n个垂直的线，每条线的两个端点是(i, ai) 和 (i, 0)。每两条线和x轴形成一个容器，求容器的最大盛水量。容器不可以倾斜，n最少取值2.

思路：暴力感觉会超时。装水量取决于较短的一条边的长度，设置双重头尾指针，如果将较长的边往中间移动，装水量只会变得更少。所以我们每次移动较短的边，看看能否把较短的边换长一点。

代码

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

人生易老，唯有陪伴最长情，加油！

以上就是关关关于这道题的总结经验，希望大家能够理解，有什么问题可以在我们的专知公众号平台上交流或者加我们的QQ专知-人工智能交流群 426491390，也可以加入专知——Leetcode刷题交流群（请先加微信小助手weixinhao: Rancho_Fang）。