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

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

点击上方“专知”，关注获取专业AI知识”

关关的刷题日记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;
    }
};