题目介绍
题目：盛最多水的容器
描述：给定 n 个非负整数 a1, a2, ..., an，每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0)。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
说明：你不能倾斜容器，且 n 的值至少为 2。
示例：
- 输入: [1,8,6,2,5,4,8,3,7]
输出: 49图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。
解析
使用暴力法可以解决此问题，但是我们当然不会这么做，因为暴力法一定会进行许多不必要的计算，这意味着我们需要设计一个更巧妙的方式，从而减少无用计算的数量。
容器的最大盛水量取决于它的短边，这是我们优化的前提。首先，我们从所有的垂直线中选择四条，它们满足以下特点：
- 有一条线最短，其它两条线都比它长，记为 线1。
- 一条线与最短线相邻，记为 线2。
- 另一条与 线2 在最短线的同一侧，且它是可以找到的距离这条短线最远的，且比它长的线，记为 线3。
- 最后一条线与 线3 相邻，且处于 线1 和 线3 之间，记为 线4。
基于以上几个规则，我们得到如下的模型，可以把它对比示例中的第 0 条、第 1 条、最后一条和倒数第二条线：
根据以上规则，我们可以得出以下几个结论：
- 以 线1 为短边的最大矩形，在这个方向上就是 线1 和 线3 组成的矩形，因为在 线3 之后没有比 线1 更长的线了。
- 如果 线1 和 线3 组成的矩形面积比 线 2 和 线 3 组成的面积小，那么在这个方向上，以 线1 为短边所能组成的全部矩形，都比 线2 和 线3 组成的矩形面积小。也就是说，计算 线1 和位于 线2 与 线3 间的所有垂直线组成的矩形面积是无用的。
- 即使 线1 和 线3 组成的矩形面积大于 线2 和 线3 组成的矩形面积，线1 和 线4 组成的矩形面积也一定小于 线2 和 线3组成的矩形面积。因为 线1 和 线4 的距离与 线2 和 线3 的距离一样，而后者的短边更长一些。
示例就可以完美的证明以上两点，对于第 0 条线而言，最后一条对应上图的 线3，倒数第二条对应 线4，第 1 条线对应 线2。以第 0 条线为短边，在它的右侧可以构成的最大矩形，就是它和最后一条线组成的矩形，其面积是 8，而第 1 条线和最后一条线所构成的面积是 49。那么第 0 条线和第 2 条线、第 3 条线，...，之间的比较都没有意义了。即使把第 0 条线的长度增加到 6，而把倒数第二条线增加到8，它们之间的矩形面积也只有 42。这样一来，第 0 条线在这个方向上的计算止步于此，后续的计算和它完全没有关系了。
现在，让我们把目光聚焦到如何解决问题上来。如果我们从左向右遍历，寻找 线1 对应的 线3，则 线3 一定是从最右侧开始的，相反，如果我们从右向左遍历，寻找 线1 对应的 线3 一定是从最左侧开始的。这意味着我们需要两个指针，一个表示短边，一个表示长边，因为对称性，有可能短边在左边，也可能长边在左边。而我们要做的就是把它们之间的矩形面积和最大面积对比，然后抛弃这个短边，把问题从 n 转化到 n-1。这个思路可以参考以下代码：
public int maxArea(int[] height) {
int max = 0;
int i = 0;
int j = height.length - 1;
while (i < j) {
int width = j - i;
// 计算短边的最大矩形面积
int area = width * Math.min(height[i], height[j]);
max = Math.max(area, max);
// 抛弃短边
if (height[i] < height[j]) {
i++;
} else {
j--;
}
}
return max;
}
总结
通过对问题的深入思考，抓住了短边决定面积这个条件，我们寻找到了时间复杂度为O(n)的解法，这再一次提醒我们不要简单的使用暴力法解决问题，而要先思考有没有更优秀的方式。
相关源码已经上传到我的Github。
下题预告
题目：整数转罗马数字
描述：罗马数字包含以下七种字符： I， V， X， L，C，D 和 M。字符 数值 I 1 V 5 X 10 L 50 C 100 D 500 M 1000例如， 罗马数字 2 写做 II ，即为两个并列的 1。12 写做 XII ，即为 X + II 。 27 写做 XXVII, 即为 XX + V + II 。
通常情况下，罗马数字中小的数字在大的数字的右边。但也存在特例，例如 4 不写做 IIII，而是 IV。数字 1 在数字 5 的左边，所表示的数等于大数 5 减小数 1 得到的数值 4 。同样地，数字 9 表示为 IX。这个特殊的规则只适用于以下六种情况：
- I 可以放在 V (5) 和 X (10) 的左边，来表示 4 和 9。
- X 可以放在 L (50) 和 C (100) 的左边，来表示 40 和 90。
- C 可以放在 D (500) 和 M (1000) 的左边，来表示 400 和 900。
给定一个整数，将其转为罗马数字。输入确保在 1 到 3999 的范围内。
示例 1:
- 输入: 3
输出: "III"示例 2:
- 输入: 4
输出: "IV"示例 3:
- 输入: 9
输出: "IX"示例 4:
- 输入: 58
输出: "LVIII"
解释: L = 50, V = 5, III = 3.示例 5:
- 输入: 1994
输出: "MCMXCIV"
解释: M = 1000, CM = 900, XC = 90, IV = 4.
我是飞机酱，如果您喜欢我的文章，可以关注我~
编程之路，道阻且长。唯，路漫漫其修远兮，吾将上下而求索。
