原题链接:http://oj.leetcode.com/problems/container-with-most-water/首先一般我们都会想到brute force的方法,思路很简单,就是对每一对pair都计算一次容积,然后去最大的那个,总共有n*(n-1)/2对pair,所以时间复杂度是O(n^2)。接下来我们考虑如何优化。思路有点类似于Two
Sum中的第二种方法--夹逼。从数组两端走起,每次迭代时判断左pointer和右pointer指向的数字哪个大,如果左pointer小,意味着向左移动右pointer不可能使结果变得更好,因为瓶颈在左pointer,移动右pointer只会变小,所以这时候我们选择左pointer右移。反之,则选择右pointer左移。在这个过程中一直维护最大的那个容积。代码如下:public int maxArea(int[] height) {
if(height==null || height.length==0)
return 0;
int l = 0;
int r = height.length-1;
int maxArea = 0;
while(l<r)
{
maxArea = Math.max(maxArea, Math.min(height[l],height[r])*(r-l));
if(height[l]<height[r])
l++;
else
r--;
}
return maxArea;
}
以上的算法,因为左pointer只向右移,右pointer只向左移,直到相遇为止,所以两者相加只走过整个数组一次,时间复杂度为O(n),空间复杂度是O(1)。该算法利用了移动指针可确定的规律,做了一步贪心,实现了时间复杂度的降低。
分享到:
相关推荐
[LeetCode] Container With Most WaterGiven n non-negative integers a1, a2, ..., a
/*中级思路以下我觉得分析有点问题*/ 中级思路, 这样的值 有两个性质, 不妨设 (i,a)为左边 (j,b)为右边为最大值, 1.若有坐标
with Ruby 13. Roman to Integer 查表,通过从前往前筛选字符串,把代表的值一个个加起来 26. Remove Duplicates from Sorted Array 难度easy的题目。根据题目要求,是不能新建数组。只能在原来的基础上做修改。基本...
指数姓名有效码无效的代码2个 3 4 5 6 7ReverseInteger.java 8 字符串到整数(atoi) StringToInteger.java StringToInteger(Invalid).java 11 装满水的容器ContainerWithMostWater.java 12 整数到罗马...
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...
Container With Most Water 盛最多水的容器 13 Roman to Integer 罗马数字转整数 14 Longest Common Prefix 最长公共前缀 20 Valid Parentheses 有效的括号 26 Remove Duplicates from Sorted Array 删除排序数组中...
分割数组求最大差值leetcode LeetCode 学习之路 记录自己完成LeetCode的代码和结果。 序号 中文名称 英文名称 通过率 难度 1 Two Sum 47.0% 简单 2 Add Two Numbers 36.0% 中等 3 Longest Substring Without ...
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 ...
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-goMy solution to LeetCode problems using GolangProblems 题库Array 数组NoTitle题名DifficultyStatus11Container With Most Water盛最多水的容器MediumSolved26Remove Duplicates from Sorted Array删除...
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-...
Water(Medium) 给定数组,作为水桶高度,序号之差作为宽度,计算最大水容量 方法: - 从头开始遍历,取两个数中小的作为高度h,序号之差作为宽度l,面积a=h*l 优化: - 从两头向中间逼近,每次移动短的边,更新最大...
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 困难 数学 ...
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...
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给单链表加一js实现 LeetCode By JavaScript LeetCode Solutions (All By JavaScript!...Water:双指针搜索的典型例子 12 Integer to Roman: 将阿拉伯数字转换为罗马数字 38 Count and Say:
lru cache leetcode leetcode leetcode solutions in C++ 微信公众号:曲奇泡芙 (互联网&车联网技术) solutions ..../0003-longest-substring-without-repeating-..../0011-container-with-most-water.cpp ./0012-int
Container With Most Water 问题简述:给出一个list a,找到一组i,j使得**min(a[i],a[j])*(j-i)**最大 思路:设置首位指针h,t 从较小的一段往中间移动,同时更新答案 12. Integer to Roman - >using this radix: ...