算法流程: 1.两个指针分别位于初始位置和结束位置 2.指针值偏小的一方往里走,同时计算面积最大值 为什么要指针值偏小的往里走? 假设左侧指针先到达最优位置(右侧同理,证明略)。如果右侧指针比左侧大,右侧指针不应该移动。理由是,假设存在右侧最优面积,右侧最优值(右边第二个线)无论是比左侧最优值高还是低,构成的面积均小于最右侧指针构成的面积。所以出现矛盾。而右侧指针比左侧小的话,就要往里走,计算比较一下可能的面积大小。
class Solution {
public:
int maxArea(vector
<int>& height
) {
int res
= 0;
for(int i
= 0, j
= height
.size() - 1; i
< j
;){
res
= max(res
, (j
- i
) * min(height
[i
], height
[j
]));
if(height
[i
] > height
[j
]) j
--;
else i
++;
}
return res
;
}
};
转载请注明原文地址:https://blackberry.8miu.com/read-38417.html