首页 > 代码库 > 【LeetCode】011 Container With Most Water
【LeetCode】011 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.
题解:
暴力解即可,注意这个面积是长方形的,我刚开始犯傻给写成梯形了。。。两个思路:两个for循环遍历,结果就是TLE了。另一个就是头尾指针遍历法,时间复杂度降为O(n).以后遇到这种需要遍历的,要先想到头尾指针法,而不是两个for循环(其实也是双指针,只是位置不一样)。同时,与之前遇到的数组问题一样,小幅度的优化就是在大循环内就跳过重复项
Solution 1 (TLE)
class Solution { public: int maxArea(vector<int>& height) { int area = 0, n = height.size(); for(int i=0; i<n-1; i++) { for(int j=i+1; j<n; j++) { int new_area = (j-i)*min(height[i], height[j]); if(height[i]==0 || height[j]==0) new_area = 0; area = max(area, new_area); } } return area; } };
Solution 2
class Solution { public: int maxArea(vector<int>& height) { int area = 0, i = 0, j = height.size() - 1; while (i < j) { area = max(area, min(height[i], height[j]) * (j - i)); height[i] < height[j] ? ++i : --j; } return area; } };
Solution 3
class Solution { public: int maxArea(vector<int>& height) { int area = 0; int i = 0, j = height.size() - 1; while (i < j) { int h = min(height[i], height[j]); area = max(area, (j - i) * h); while (height[i] <= h && i < j) i++; while (height[j] <= h && i < j) j--; } return area; } };
【LeetCode】011 Container With Most Water
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。