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.
注意这里的Note:和装的东西是水,就是最短木板原理:一个桶能装多少水是由最短的那块木板决定的。
一开始没搞清楚这一点,误以为是比较梯形的面积,所以做错了。
其实这个是动态规划法做的,因为我没看到有人分析其中的动态规划法思想,所以在这里分析一下。
下面分析是怎么样的动态规划法思想。
1 分区,首先分最大区间,左边高度为height[0],右边高度为height[n-1], 分一个区间,那么这个区间的解肯定是height[0]和height[n-1]围成的区间
2 区间细分,分两个区间height[0]和height[n-2],还有height[1]和height[n]也构成一个区间,这个区间的最大木桶容水量和前面比较,这个值也可以用表保存下来,但是因为我们不需要中间结果,所以不需要保存一个表,只需要保存最大值就可以了。
3 继续细分为3个区间,然后4个区间,……直到n-1个区间。
但是这道题就巧妙的利用了一个木桶和装水的特征,可以更加优化一点。不过其实也是动态规划法原理。至于怎么利用这个特征,很多博客都有分析了,我就不在这里重复了。随便百度就可以了。我只是没看到有人分析这里的动态规划法的思想,所以分析一下。
看看LeetCode上有人贴出的程序:
http://discuss.leetcode.com/questions/193/container-with-most-water
int maxArea(vector<int> &height) {
int i = 0;
int j = height.size() - 1;
int res = 0;
while(i < j)
{
int temp = min(height[i], height[j]) * (j - i);
if(temp > res)
res = temp;
if(height[i] <= height[j])
i++;
else
j--;
}
return res;
}
分享到:
相关推荐
[LeetCode] Container With Most WaterGiven n non-negative integers a1, a2, ..., a
/*中级思路以下我觉得分析有点问题*/ 中级思路, 这样的值 有两个性质, 不妨设 (i,a)为左边 (j,b)为右边为最大值, 1.若有坐标
leetcode刷题之动态规划
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...
leetcode思维导图-动态规划
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...
刷LeetCode刷LeetCode刷LeetCode刷LeetCode刷LeetCode
颜色分类leetcode My Leetcode Problems Solutions Using javascript(ES6) 1 Two Sum 两数之和 5 Longest Palindromic Substring 最长回文子串 7 Reverse Integer 整数反转 9 Palindrome Number 回文数 11 Container...
算法相关知识储备 LeetCode with Python
LeetCode, LintCode题解分析
javascript javascript_leetcode面试题解动态规划问题之第221题最大正方形_题解
java;LeetCode前一百道;有题目;多重解法
算法 Leetcode刷题手册 labuladong的算法小抄官方完整版
由于本算法用了动态规划的思想,所以对动态规划做一个简单的总结。 动态规划 简介 动态规划算法通常基于一个递推公式及一个或多个初始状态。当前子问题的解将由上一次子问题的解推出。使用动态规划来解题只需要...
动态规划,英⽂:Dynamic Programming,简称DP,如果某⼀问题有很多重叠⼦问题,使⽤动态规划是最有效的。 所以动态规划中每⼀个状态⼀定是由上⼀个状态推导出来的,这⼀点就区分于贪⼼,贪⼼没有状态推导,⽽是从...
javascript javascript_leetcode面试题解动态规划问题之第53题最大子序和_题解
javascript javascript_leetcode面试题解动态规划问题之第152题乘积最大子数组_题解
leetcode04_寻找两个正序数组的中位数解法.rar !!!CSDN的一个特性: 即使我设置成免费下载,被下载的次数多了之后也会变成付C币下载的了,这个很头疼. !!!因此如果没有C币但想要下载的朋友可以在b站视频下留言给我,留下...
javascript javascript_leetcode面试题解动态规划问题之第1423题可获得的最大点数_题解
二分查找Binary_Search套路和解题模板【LeetCode刷题套路教程3】