logo
Redian新闻
>未名空间
>JobHunting - 待字闺中
>
求OJ container with most water O(n)解法
avatar
求OJ container with most water O(n)解法# JobHunting - 待字闺中
w*x
1 楼
Given n non-negative integers a1, a2, ..., an, where each represents a point
at coordinate (i, ai). n vertical lines are drawn such that the two
endpoints of line i is at (i, ai) 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.
[2,3,10,5,7,8,9] => 36 => 10...9
给个O(n)解法的思路？？
avatar
Z*Z
2 楼
头尾两个指针从前、后扫。谁短就移谁。

point
together

【在 w****x 的大作中提到】
: Given n non-negative integers a1, a2, ..., an, where each represents a point
: at coordinate (i, ai). n vertical lines are drawn such that the two
: endpoints of line i is at (i, ai) 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.
: [2,3,10,5,7,8,9] => 36 => 10...9
: 给个O(n)解法的思路？？
avatar
w*x
3 楼

怎么证明？

【在 Z*****Z 的大作中提到】
: 头尾两个指针从前、后扫。谁短就移谁。
:
: point
: together
avatar
l*c
4 楼
这题，我要能不用O(N^2)解出来我就挺高兴的了。。。。
avatar
Z*Z
5 楼
BF的写法，O（N2），可以是：
for(start = 0; start < len; start ++){
for(end = len-1; len > start; len--){
//...
}
}
然后你想，如果某一个end已经比start高了，再往近挪就没意义了，因为这个时候star
t是短板，再挪面积只能减小。这种情况下就可以skip剩下的end。
同理，对，start也一样。

【在 w****x 的大作中提到】
:
: 怎么证明？
avatar
w*x
6 楼
我有个nlogn的解法，建立一个structure {value, index}, 根据value增序排序，然后
用一个iterator, 这个iterator假设为最小边， 从右往左扫， 过程中记录最大index
和最小index, 扫一遍， 就成了股票买卖问题。
avatar
w*x
7 楼

star
了解，这真不大容易想出来

【在 Z*****Z 的大作中提到】
: BF的写法，O（N2），可以是：
: for(start = 0; start < len; start ++){
: for(end = len-1; len > start; len--){
: //...
: }
: }
: 然后你想，如果某一个end已经比start高了，再往近挪就没意义了，因为这个时候star
: t是短板，再挪面积只能减小。这种情况下就可以skip剩下的end。
: 同理，对，start也一样。
avatar
l*c
8 楼
那要是有一边一直越来越小，直到最后挪了个最小的，就不行了啊。
需要存下一个暂时最大的？

star

【在 Z*****Z 的大作中提到】
: BF的写法，O（N2），可以是：
: for(start = 0; start < len; start ++){
: for(end = len-1; len > start; len--){
: //...
: }
: }
: 然后你想，如果某一个end已经比start高了，再往近挪就没意义了，因为这个时候star
: t是短板，再挪面积只能减小。这种情况下就可以skip剩下的end。
: 同理，对，start也一样。
avatar
Z*Z
9 楼
对。如果是 5,4,3,2,1,10，那么上来的那个解就是最大的。

【在 l****c 的大作中提到】
: 那要是有一边一直越来越小，直到最后挪了个最小的，就不行了啊。
: 需要存下一个暂时最大的？
:
: star
avatar
w*x
10 楼

膜拜啊~~~~

【在 Z*****Z 的大作中提到】
: 对。如果是 5,4,3,2,1,10，那么上来的那个解就是最大的。
avatar
Z*Z
11 楼
leetcode俯视笑而不语。。。

【在 w****x 的大作中提到】
:
: 膜拜啊~~~~
avatar
w*x
12 楼

star
奇怪，你是怎么一步步想到的，我两边夹的题也做了不少，我怎么想不到，真是猪脑啊
~~~~

【在 Z*****Z 的大作中提到】
: BF的写法，O（N2），可以是：
: for(start = 0; start < len; start ++){
: for(end = len-1; len > start; len--){
: //...
: }
: }
: 然后你想，如果某一个end已经比start高了，再往近挪就没意义了，因为这个时候star
: t是短板，再挪面积只能减小。这种情况下就可以skip剩下的end。
: 同理，对，start也一样。
avatar
i*e
13 楼
佩服。
avatar
p*2
14 楼

你两边夹的太多了，麻木了吧？

【在 w****x 的大作中提到】
:
: star
: 奇怪，你是怎么一步步想到的，我两边夹的题也做了不少，我怎么想不到，真是猪脑啊
: ~~~~
avatar
z*e
15 楼
怎么感觉这题像是数组元素围成最大矩形的变形
avatar
w*x
16 楼
Given n non-negative integers a1, a2, ..., an, where each represents a point
at coordinate (i, ai). n vertical lines are drawn such that the two
endpoints of line i is at (i, ai) 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.
[2,3,10,5,7,8,9] => 36 => 10...9
给个O(n)解法的思路？？
avatar
Z*Z
17 楼
头尾两个指针从前、后扫。谁短就移谁。

point
together

【在 w****x 的大作中提到】
: Given n non-negative integers a1, a2, ..., an, where each represents a point
: at coordinate (i, ai). n vertical lines are drawn such that the two
: endpoints of line i is at (i, ai) 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.
: [2,3,10,5,7,8,9] => 36 => 10...9
: 给个O(n)解法的思路？？
avatar
w*x
18 楼

怎么证明？

【在 Z*****Z 的大作中提到】
: 头尾两个指针从前、后扫。谁短就移谁。
:
: point
: together
avatar
l*c
19 楼
这题，我要能不用O(N^2)解出来我就挺高兴的了。。。。
avatar
Z*Z
20 楼
BF的写法，O（N2），可以是：
for(start = 0; start < len; start ++){
for(end = len-1; len > start; len--){
//...
}
}
然后你想，如果某一个end已经比start高了，再往近挪就没意义了，因为这个时候star
t是短板，再挪面积只能减小。这种情况下就可以skip剩下的end。
同理，对，start也一样。

【在 w****x 的大作中提到】
:
: 怎么证明？
avatar
w*x
21 楼
我有个nlogn的解法，建立一个structure {value, index}, 根据value增序排序，然后
用一个iterator, 这个iterator假设为最小边， 从右往左扫， 过程中记录最大index
和最小index, 扫一遍， 就成了股票买卖问题。
avatar
w*x
22 楼

star
了解，这真不大容易想出来

【在 Z*****Z 的大作中提到】
: BF的写法，O（N2），可以是：
: for(start = 0; start < len; start ++){
: for(end = len-1; len > start; len--){
: //...
: }
: }
: 然后你想，如果某一个end已经比start高了，再往近挪就没意义了，因为这个时候star
: t是短板，再挪面积只能减小。这种情况下就可以skip剩下的end。
: 同理，对，start也一样。
avatar
l*c
23 楼
那要是有一边一直越来越小，直到最后挪了个最小的，就不行了啊。
需要存下一个暂时最大的？

star

【在 Z*****Z 的大作中提到】
: BF的写法，O（N2），可以是：
: for(start = 0; start < len; start ++){
: for(end = len-1; len > start; len--){
: //...
: }
: }
: 然后你想，如果某一个end已经比start高了，再往近挪就没意义了，因为这个时候star
: t是短板，再挪面积只能减小。这种情况下就可以skip剩下的end。
: 同理，对，start也一样。
avatar
Z*Z
24 楼
对。如果是 5,4,3,2,1,10，那么上来的那个解就是最大的。

【在 l****c 的大作中提到】
: 那要是有一边一直越来越小，直到最后挪了个最小的，就不行了啊。
: 需要存下一个暂时最大的？
:
: star
avatar
w*x
25 楼

膜拜啊~~~~

【在 Z*****Z 的大作中提到】
: 对。如果是 5,4,3,2,1,10，那么上来的那个解就是最大的。
avatar
Z*Z
26 楼
leetcode俯视笑而不语。。。

【在 w****x 的大作中提到】
:
: 膜拜啊~~~~
avatar
w*x
27 楼

star
奇怪，你是怎么一步步想到的，我两边夹的题也做了不少，我怎么想不到，真是猪脑啊
~~~~

【在 Z*****Z 的大作中提到】
: BF的写法，O（N2），可以是：
: for(start = 0; start < len; start ++){
: for(end = len-1; len > start; len--){
: //...
: }
: }
: 然后你想，如果某一个end已经比start高了，再往近挪就没意义了，因为这个时候star
: t是短板，再挪面积只能减小。这种情况下就可以skip剩下的end。
: 同理，对，start也一样。
avatar
i*e
28 楼
佩服。
avatar
p*2
29 楼

你两边夹的太多了，麻木了吧？

【在 w****x 的大作中提到】
:
: star
: 奇怪，你是怎么一步步想到的，我两边夹的题也做了不少，我怎么想不到，真是猪脑啊
: ~~~~
avatar
z*e
30 楼
怎么感觉这题像是数组元素围成最大矩形的变形
avatar
l*r
31 楼
Can any explain what the question means?
"find two lines, which with x axis", 3 lines to form a triangle container?
相关阅读
找工作流水账（5）JP Morgan phone interview questions反面教材-Google的Phone Interview经验记一次失败的面试找工作流水账（3）我这找工作的九个月（－）面试流水帐经历说说这cs的工作找工作的一些心得-关于招聘会面经二：如何对付tough technical questions说说我的非热门专业找工的经验吧 MEOPT expedite letter[合集] My solution Re: 网上看到一道google面试题on-site interview经验说一说我的看法 我这找工作的九个月（二）心得体会说说昨天的Cisco onsiteONSITE回来...写点儿什么吧My Microsoft Phone Interviewsecond round amazon interview发点面试题讨包子(cs)
logo
联系我们隐私协议©2024 redian.news
Redian新闻
Redian.news刊载任何文章，不代表同意其说法或描述，仅为提供更多信息，也不构成任何建议。文章信息的合法性及真实性由其作者负责，与Redian.news及其运营公司无关。欢迎投稿，如发现稿件侵权，或作者不愿在本网发表文章，请版权拥有者通知本网处理。