[LeetCode]Container With Most Water(中期有问题仅供参考)1
需积分: 0 193 浏览量
2022-08-08
21:33:39
上传
评论
收藏 26KB DOCX 举报
[LeetCode]Container With Most Water
分类： LeetCode2012-11-14 16:12 156 人阅读 评论(0) 收藏 举报
Given n non-negative integers a
1
, a
2
, ..., a
n
, where each represents a point at coordinate
(i, a
i
). n vertical lines are drawn such that the two endpoints of line i is at (i, a
i
) 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.
简单翻译： 有一些竖线，坐标分别是 (i,a
i
); 问选 其中两条线 作为容器的两侧 ，X 轴为底边，
最大容量是多少。
如果选择 （i, a）(j,b) 那么容量就是 |i-j| * min(a,b) 。
初级思路，遍历，所有坐标， 复杂度 O（n^2） ，选最大值。 小数据能过，大数据果断超时。
/*中级思路以下我觉得分析有点问题*/
中级思路， 这样的值 有两个性质， 不妨设 （i,a）为左边 （j,b）为右边为最大值，
1.若有坐标( j+k，c)，k>0 必然 b>c ，否则（i,a）(j+k, c) 的容积 (k+j-i)*min(a,c) 大于
（j-i）*min(a,b) 即 b 比右边的坐标都大
2. 同理， a 比 左边的坐标值都大所以，可以做预处理，把 比左边的大的坐标，标记出来，
把比右边都大的坐标也标记出来。
例如：如下数组，第一个坐标是（0，5），第二坐标（1，2），最后一个是（9，4）；
5
2
12
1
5
3
4
11
9
4
1
0
1
0
0
0
0
0
0
0
0
0
1
0
0
0
0
1
1
1
第一行是 ai， 第二行是左标记，第三行 右标记 ，标记的复杂度是 O（n） 。
求解的遍历方式：i 从 0 开始 j 从 size（）-1 开始， i<j ; i 和 j 仅取相应的标记值的值。
这是相当于一个较大的剪枝， 大数据能过。
代码如下：
[cpp] view plaincopy
1. class Solution {
2. public:
3. int maxArea(vector<int> &height) {
4. // Start typing your C/C++ solution below
5. // DO NOT write int main() function
评论0