Container With Most Water
哎，最近心情烦躁，想在leetcode找找感觉，就看到了这题。
然而，看了题目半天，硬是没看懂，于是乎就百度了下，怕看到解题方法，就略看了下摘要，以为懂了，万万没想到，居然把题目意思理解错了，所以还是要好好学英语呀。
然而，在理解对了之后，又是time limit excess，又瞟了下博客讲解，也算是徒手码了出来，记录一发，随便再体会下....
题目相关
题目在这，Container With Most Water
大概意思就是，给出的各点作x轴垂线，与x轴组成一个Container，然后找出两条线，使得其能储存最大容量的水，哎，其实仔细看题目，人家表述的很清楚呀，好好学英语呀...
思路一
正确理解题目了之后，按照我等弱鸡智商当然是第一反应是遍历了，很简单，两边两块板，容量为：
min*(j-i)
选取一边作为基准，遍历其后面的所有边，与之形成容器，得到各个容量。
两个循环就行...
好久没用js了，就熟悉下。
Algorithm = {};
Algorithm.private = {};
Algorithm.private.GetArea = function (height, i, j) {
var min = 0;
if (height[i] > height[j]) {
min = height[j];
} else {
min = height[i];
}
return min * (j - i);
}
Algorithm.ContainerWater = function (height) {
var maxArea = 0;
for (var i = 0; i < height.length; i++) {
for (var j = i; j < height.length; j++) {
var t = Algorithm.private.GetArea(height, i, j)
if (maxArea < t) {
maxArea = t;
}
}
}
return maxArea;
}
毫无疑问，时间超时，不过好歹也能工作吧.....
思路二
看了下别人的思路，原来，还可以这样
最终找到了两条线应该具备以下两个性质
- 左边的线的左边不会有比其更长的线
- 右边的线的右边不会有比其更长的线
其实很好理解，如果所找到的结果不满足这两条性质，那这结果必然不是最优的，也即是说，上面两点是必要条件，由此，得到以下代码...
Algorithm.ContainerWaterOpt = function (height) {
var a = [], b = [], amax = 0, bmax = 0, maxArea = 0;
for (var i = 0; i < height.length; i++) {
if (amax < height[i]) {
amax = height[i];
a.push(i);
}
if (bmax < height[height.length - i - 1]) {
bmax = height[height.length - i - 1];
b.push(height.length - i - 1);
}
}
for (var i = 0; i < a.length; i++) {
for (var j = 0; j < b.length; j++) {
var t = Algorithm.private.GetArea(height, a[i], b[j]);
if (maxArea < t) {
maxArea = t;
}
}
}
return maxArea;
}
后记
哎，以后做题时，还是好好思考题目本身里面的内涵，不一定非要从数据结构等来思考...
最最重要的，好好学英语呀！