Givennnon-negative integersa1,a2,
...,an, where each represents a point at coordinate (i,ai).nvertical
lines are drawn such that the two endpoints of lineiis 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.
这一题的解题思路在于，其实不需要n^2的复杂度去遍历所有的左右边组合，只需要从两头网中间找，短边移动，碰到比该边大的边就计算容积是否满足大于原来容积的条件在，这样复杂度是n。
public class Solution {
public int maxArea(int[] height) {
int i=0,j=height.length-1;
int max=height[i]>height[j]?(height[j]*j):(height[i]*j);
while(i<j){
if(height[i]<height[j]){
int l=height[i];
while(height[i]<=l&&i<j)
i++;
int s=height[i]<height[j]?height[i]*(j-i):height[j]*(j-i);
if(s>max)
max=s;
}else{
int m=height[j];
while(height[j]<=m&&i<j)
j--;
int s=height[i]<height[j]?height[i]*(j-i):height[j]*(j-i);
if(s>max)
max=s;
}
}
return max;
}
}
分享到：
相关推荐
[LeetCode] Container With Most WaterGiven n non-negative integers a1, a2, ..., a
/*中级思路以下我觉得分析有点问题*/ 中级思路， 这样的值 有两个性质， 不妨设 （i,a）为左边 （j,b）为右边为最大值， 1.若有坐标
Container With Most Water LeetCode 19 Remove Nth Node From End of List LeetCode 42 Trapping Rain Water LeetCode 61 RotateList LeetCode 75 Sort Colors LeetCode 125 Valid Palindrome LeetCode 167 Two Sum...
11. Container With Most Water 13. Roman to Integer 15. 3Sum 16. 3Sum Closest 17. Letter Combinations of a Phone Number 18. 4Sum 19. Remove Nth Node From End of List 20. Valid Parentheses 21. Merge Two...
Container with Most Water 14 Longest Common Prefix 15 Three Sum 16 Three Sum Closest 20 Valid Parentheses 26 Remove Duplicates from Sorted Array 48 Rotate Image 53 Maximum Subarray 55 Jump Game 56 ...
Container With Most Water 盛最多水的容器 13 Roman to Integer 罗马数字转整数 14 Longest Common Prefix 最长公共前缀 20 Valid Parentheses 有效的括号 26 Remove Duplicates from Sorted Array 删除排序数组中...
with Ruby 13. Roman to Integer 查表，通过从前往前筛选字符串，把代表的值一个个加起来 26. Remove Duplicates from Sorted Array 难度easy的题目。根据题目要求，是不能新建数组。只能在原来的基础上做修改。基本...
Container With Most Water 12. Integer to Roman 13. Roman to Integer 14. Longest Common Prefix 15. 3Sum 20. Valid Parentheses 21. Merge Two Sorted Lists 22. Generate Parentheses 25. Reverse Nodes in k-...
Container With Most Water 中等 12 Integer to Roman 中等 13 Roman to Integer 简单 14 Longest Common Prefix 简单 15 3Sum 中等 16 3Sum Closest 中等 17 Letter Combinations of a Phone Number DFS 中等 18 4...
leetcode双人赛LeetCode 编号 题目 难度 题型 备注 Two Sum 简单 Add Two Numbers 中等 链结串列 重要 Longest Substring Without Repeating Characters 中等 字串 重要 Median of Two Sorted Arrays 困难 数学 ...
LeetCode刷题总结 1.Two Sum 2.Add Two Numbers 3.Longest Substring Without Repeating Characters 4.Median of Two Sorted Arrays 5.Longest Palindromic Substring (Manacher算法待完成) 6.ZigZag Conversion 7....
分割数组求最大差值leetcode LeetCode 学习之路 记录自己完成LeetCode的代码和结果。 序号 中文名称 英文名称 ...Container With Most Water 59.3% 中等 12 Integer to Roman 61.8% 中等 13 Roman to In
Leetcode回文串拼接 ...11.Container With Most Water 12.Integer To Roman 13.Roman To Integer 289 347 380 442 457 Circular Array Loop 535 Encode and Decode TinyURL 560 565 566 Maximum Binary T
Container With Most Water 012 Integer to Roman 013 Roman to Integer 014 Longest Common Prefix 015 3Sum 016 3Sum Closest 017 Letter Combinations of a Phone Number 018 4Sum 020 Valid Parentheses 022 ...
指数姓名有效码无效的代码2个 3 4 5 6 7ReverseInteger.java 8 字符串到整数（atoi） StringToInteger.java StringToInteger（Invalid）.java 11 装满水的容器ContainerWithMostWater.java 12 整数到罗马...
Water(Medium) 给定数组，作为水桶高度，序号之差作为宽度，计算最大水容量 方法： - 从头开始遍历，取两个数中小的作为高度h，序号之差作为宽度l，面积a=h*l 优化： - 从两头向中间逼近，每次移动短的边，更新最大...
35%2☆ ☆27%3☆ ☆24%4☆ ☆ ☆21%5☆ ☆25%6☆ ☆26%7☆24%8☆ ☆13%9Palindrome Number☆35%10Regular Expression Matching☆ ☆ ☆24%:red_heart:11Container With Most Water☆ ☆36%12Integer to R
Container With Most Water 这里题目的分析图如下： 所以我们需要找的是ai，aj中的最小值作为高，然后找(i-j)的最大值作为长 然后得到最大的容积。 所以我们这样做 用两个point来记录现在所在的x坐标（即i值） 然后...
leetcode Python 001 leetcode的算法问题 这是我的解决方案，用 cpp 、 java 和 python ...Container With Most Water 012. Integer to Roman 013. Roman to Integer 014. Longest Common Prefix 019. R
LC11_ContainerWithMostWater.py ├── LC121_BestTimetoBuyAndSellStock.py ├── LC12_IntToRoman.py ├── LC13_RomanToInt.py ├── LC144_BinaryTreePreorderTraversal.py ├── LC14_longestCommonPrefix...