- 浏览: 89446 次
- 性别:
- 来自: 南京
最新评论
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.
此题最土的可以用O(N^2)来搞,但是请相信我。这么搞是行不通的。
分析一下问题:要存放最多的水,那么是求出min(height[i], height[j]) * (j - i)中的最大值,其中j > i;
i~j存水的大小,是由min(height[i], height[j])来决定的。
如果height[i] > height[j],且i+1~j可以更多,必然有height[i+1] > height[i].
如果height[i] < height[j],且i~j-1可以更多,必然有height[j-1] > height[j].
因此,每次通过调整短板min(height[i], height[j])来找更大的容量。
贪心O(n).
ij分别从两端开始走。每次移动短板。
#define min(a,b) ((a) > (b) ? (b) : (a)) #define max(a,b) ((a) > (b) ? (a) : (b)) class Solution { public: int maxArea(vector<int> &height) { int res = -1; int i = 0; int j = height.size() - 1; int m; while (i < j) { m = min(height[i], height[j]); res = max(res, (j-i)*m); if (height[i] == m) { i++; } else { j--; } } return res; } };
发表评论
-
[Leetcode] Gas Station
2013-10-07 00:02 929Gas Station AC Rate: 101 ... -
[Leetcode] Word Break 1 & 2
2013-10-05 23:26 1376Word Break AC Rate: 2/1 ... -
[Leetcode] Single Number 1 & 2
2013-10-05 22:50 2765Single Number AC Rat ... -
[Leetcode] Copy List with Random Pointer
2013-10-05 22:43 587Copy List with Random Pointe ... -
[Leetcode] Path Sum
2013-10-03 23:52 599Path Sum AC Rate: 87 ... -
[Leetcode] Remove Duplicates from Sorted List 1 & 2
2013-10-03 23:34 981Remove Duplicates from Sort ... -
[Leetcode] Scramble String
2013-10-03 16:55 1843Scramble String AC Rate ... -
[Leetcode] Partition List
2013-09-29 23:38 670Partition List AC Rate: ... -
[Leetcode] Word Search
2013-09-21 23:21 861Given a 2D board and ... -
[Leetcode] Decode Ways
2013-09-11 17:33 692Decode WaysJun 25 '126747 / 2 ... -
[Leetcode] Convert Sorted List to Binary Search Tree
2013-09-11 16:06 722Convert Sorted List to Binary ... -
[Leetcode] Binary Tree Level Order Traversal
2013-09-10 14:39 787Binary Tree Level Order Trave ... -
[Leetcode] Subsets 1 ^& 2
2013-09-09 21:42 875SubsetsApr 18 '126226 / 1626 ... -
[Leetcode] Unique Paths II
2013-09-09 21:10 768Unique Paths IIMar 29 '124573 ... -
[Leetcode] Flatten Binary Tree to Linked List
2013-09-09 02:35 731Flatten Binary Tree to Linked ... -
[Leetcode] Triangle
2013-09-04 16:32 934TriangleOct 30 '126503 / 1779 ... -
[Leetcode] Balanced Binary Tree
2013-08-27 20:53 614Balanced Binary TreeOct 9 '12 ... -
[Leetcode] Rotate Image
2013-08-22 15:54 980Rotate ImageMar 18 '124182 / ... -
[Leetcode] Permutations / Permutations II
2013-08-22 15:41 2512Permutations IIMar 17 '12494 ... -
[Leetcode] Jump Game / Jump Game II
2013-08-22 10:31 663Jump GameMar 25 '126923 / 162 ...
相关推荐
[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...