Container With Most Water
从两侧开始，每次矮的边界向中间移动。如果两侧相同则随意移动。
- 求出结果的过程与某个最优解总会有某一刻有相同的某一个边界，但宽度为>=的关系；
- 如最优为a-b，过程中找到的是c-b，则a>=c；
- 现在只考虑a>c的情况；反之已经找到最优解，之后如果找到更好的就说明不是最优解；同时可以左右交换以考虑对称的情况；
- 在这一个边界时，若求出结果这一刻的体积小于这个最优解的时刻，则另一个边界是小于关系，因此会向右移动；
- 即一定有c<b，否则不会更优；
- 所以会移动左边界向内，如果不到最优解那里，则肯定还是c’<b，否则比最优解更优。
- 如果两侧边界相同，则说明更优时两个边界都得增加，否则不会比现在大。
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
| class Solution {
public:
int maxArea(vector<int>& height) {
int left = 0, right = height.size() - 1;
int ans = (left < right ? left : right) * (right - left), tempans = 0;
while (left < right) {
if height[left] < height[right] {
int temp = left + 1;
while (height[left] >= height[temp] && temp < right) {
temp++;
}
left = temp;
}
else {
int temp = right - 1;
while (height[right] >= height[temp] && temp > left) {
temp--;
}
right = temp;
}
tempans = (left < right ? left : right) * (right - left);
ans = ans < tempans ? tempans : ans;
}
return ans;
}
};
|
其实并不需要