Maximum Number in Mountain Sequence
.everyoneloves__top-leaderboard:empty,.everyoneloves__mid-leaderboard:empty,.everyoneloves__bot-mid-leaderboard:empty{ height:90px;width:728px;box-sizing:border-box;
}
Given a mountain sequence of n integers which increase firstly and then decrease, find the mountain top.
Example
Given nums = [1, 2, 4, 8, 6, 3] return 8
Given nums = [10, 9, 8, 7], return 10
class Solution:
"""
@param nums: a mountain sequence which increase firstly and then decrease
@return: then mountain top
"""
def mountainSequence(self, nums):
# write your code here
if nums == :
return None
if len(nums) <= 1:
return nums[0]
elif len(nums) <= 2:
return max(nums[0], nums[1])
for i in range(len(nums) -2):
if nums[i] >= nums[i + 1]:
return nums[i]
return nums[-1]
it stuck at [3,5,3]. Based on my analysis, it went wrong after running the for loop. But I cannot figure it out why the for loop failed.
python-3.x for-loop
asked Nov 16 '18 at 17:02
Wei BoveyWei Bovey
1514
add a comment |
Given a mountain sequence of n integers which increase firstly and then decrease, find the mountain top.
Example
Given nums = [1, 2, 4, 8, 6, 3] return 8
Given nums = [10, 9, 8, 7], return 10
class Solution:
"""
@param nums: a mountain sequence which increase firstly and then decrease
@return: then mountain top
"""
def mountainSequence(self, nums):
# write your code here
if nums == :
return None
if len(nums) <= 1:
return nums[0]
elif len(nums) <= 2:
return max(nums[0], nums[1])
for i in range(len(nums) -2):
if nums[i] >= nums[i + 1]:
return nums[i]
return nums[-1]
it stuck at [3,5,3]. Based on my analysis, it went wrong after running the for loop. But I cannot figure it out why the for loop failed.
python-3.x for-loop
asked Nov 16 '18 at 17:02
Wei BoveyWei Bovey
1514
given you do not try a binary search (and maybe you should); why not justmax(nums)?
– hiro protagonist
Nov 16 '18 at 17:05
10 is not a mountain - it does not increase beforehand only decrease after
– Patrick Artner
Nov 16 '18 at 17:09
what about plateaus:7, 8, 9, 9, 9, 8, 7?
– Patrick Artner
Nov 16 '18 at 17:11
actually its not allowed to use max(). I was just being lazy to write some more if. LOL
– Wei Bovey
Nov 16 '18 at 17:16
1
You're providing a wrong argument to the range function and the loop is missing one element. Change it forrange(len(nums) - 1).
– fsinisi90
Nov 16 '18 at 17:24
add a comment |
Given a mountain sequence of n integers which increase firstly and then decrease, find the mountain top.
Example
Given nums = [1, 2, 4, 8, 6, 3] return 8
Given nums = [10, 9, 8, 7], return 10
class Solution:
"""
@param nums: a mountain sequence which increase firstly and then decrease
@return: then mountain top
"""
def mountainSequence(self, nums):
# write your code here
if nums == :
return None
if len(nums) <= 1:
return nums[0]
elif len(nums) <= 2:
return max(nums[0], nums[1])
for i in range(len(nums) -2):
if nums[i] >= nums[i + 1]:
return nums[i]
return nums[-1]
it stuck at [3,5,3]. Based on my analysis, it went wrong after running the for loop. But I cannot figure it out why the for loop failed.
python-3.x for-loop
asked Nov 16 '18 at 17:02
Wei BoveyWei Bovey
1514
Given a mountain sequence of n integers which increase firstly and then decrease, find the mountain top.
Example
Given nums = [1, 2, 4, 8, 6, 3] return 8
Given nums = [10, 9, 8, 7], return 10
class Solution:
"""
@param nums: a mountain sequence which increase firstly and then decrease
@return: then mountain top
"""
def mountainSequence(self, nums):
# write your code here
if nums == :
return None
if len(nums) <= 1:
return nums[0]
elif len(nums) <= 2:
return max(nums[0], nums[1])
for i in range(len(nums) -2):
if nums[i] >= nums[i + 1]:
return nums[i]
return nums[-1]
it stuck at [3,5,3]. Based on my analysis, it went wrong after running the for loop. But I cannot figure it out why the for loop failed.
python-3.x for-loop
python-3.x for-loop
asked Nov 16 '18 at 17:02
Wei BoveyWei Bovey
1514
asked Nov 16 '18 at 17:02
Wei BoveyWei Bovey
1514
asked Nov 16 '18 at 17:02
Wei BoveyWei Bovey
1514
asked Nov 16 '18 at 17:02
Wei BoveyWei Bovey
1514
asked Nov 16 '18 at 17:02
Wei BoveyWei Bovey
1514
1514
given you do not try a binary search (and maybe you should); why not justmax(nums)?
– hiro protagonist
Nov 16 '18 at 17:05
10 is not a mountain - it does not increase beforehand only decrease after
– Patrick Artner
Nov 16 '18 at 17:09
what about plateaus:7, 8, 9, 9, 9, 8, 7?
– Patrick Artner
Nov 16 '18 at 17:11
actually its not allowed to use max(). I was just being lazy to write some more if. LOL
– Wei Bovey
Nov 16 '18 at 17:16
1
You're providing a wrong argument to the range function and the loop is missing one element. Change it forrange(len(nums) - 1).
– fsinisi90
Nov 16 '18 at 17:24
add a comment |
given you do not try a binary search (and maybe you should); why not justmax(nums)?
– hiro protagonist
Nov 16 '18 at 17:05
10 is not a mountain - it does not increase beforehand only decrease after
– Patrick Artner
Nov 16 '18 at 17:09
what about plateaus:7, 8, 9, 9, 9, 8, 7?
– Patrick Artner
Nov 16 '18 at 17:11
actually its not allowed to use max(). I was just being lazy to write some more if. LOL
– Wei Bovey
Nov 16 '18 at 17:16
1
You're providing a wrong argument to the range function and the loop is missing one element. Change it forrange(len(nums) - 1).
– fsinisi90
Nov 16 '18 at 17:24
given you do not try a binary search (and maybe you should); why not just
max(nums)?– hiro protagonist
Nov 16 '18 at 17:05
given you do not try a binary search (and maybe you should); why not just
max(nums)?– hiro protagonist
Nov 16 '18 at 17:05
10 is not a mountain - it does not increase beforehand only decrease after
– Patrick Artner
Nov 16 '18 at 17:09
10 is not a mountain - it does not increase beforehand only decrease after
– Patrick Artner
Nov 16 '18 at 17:09
what about plateaus:
7, 8, 9, 9, 9, 8, 7 ?– Patrick Artner
Nov 16 '18 at 17:11
what about plateaus:
7, 8, 9, 9, 9, 8, 7 ?– Patrick Artner
Nov 16 '18 at 17:11
actually its not allowed to use max(). I was just being lazy to write some more if. LOL
– Wei Bovey
Nov 16 '18 at 17:16
actually its not allowed to use max(). I was just being lazy to write some more if. LOL
– Wei Bovey
Nov 16 '18 at 17:16
1
1
You're providing a wrong argument to the range function and the loop is missing one element. Change it for
range(len(nums) - 1).– fsinisi90
Nov 16 '18 at 17:24
You're providing a wrong argument to the range function and the loop is missing one element. Change it for
range(len(nums) - 1).– fsinisi90
Nov 16 '18 at 17:24
add a comment |
2 Answers
2
active
oldest
votes
this should be more efficient than your approach. it is a binary search customized for your use-case:
def top(lst):
low = 0
high = len(lst)
while low != high:
i = (high+low)//2
if lst[i] < lst[i+1]:
low = i+1
else:
high = i
return low
it starts in the middle of the list and checks if the series is still increasing there. if it is it sets low and will ignore all indices below low for the rest of the algorithm. if the series decreases already, high is set to the current index and all the elements above are ignored. and so on... when high == low the algorithm terminates.
if you have two or more of the same elements at the maximum of your list (a plateau) the algorithm will not even terminate.
and i skipped the tests for empty lists or lists of length 1.
answered Nov 16 '18 at 17:15
hiro protagonisthiro protagonist
20.7k74264
Thank you for your answer. I know the binary search solution. I just want to figure out what's wrong with my code. But thx!
– Wei Bovey
Nov 16 '18 at 19:11
you ignore the last element in your lastforloop... should berange(len(nums) - 1).
– hiro protagonist
Nov 16 '18 at 19:37
OMG! Gotcha! Thank you so much!
– Wei Bovey
Nov 18 '18 at 18:47
add a comment |
This will get all triplets from your input, isolate all that are higher in the middle then left or right and return the one that is highest overall:
def get_mountain_top(seq):
triplets = zip(seq, seq[1:], seq[2:])
tops = list(filter(lambda x: x[0] < x[1] > x[2], triplets))
if tops:
# max not allowed, leverage sorted
return sorted(tops, key = lambda x:x[1])[-1]
# return max(tops,key = lambda x:x[1])
return None
print(get_mountain_top([1,2,3,4,3,2,3,4,5,6,7,6,5]))
print(get_mountain_top([1,1,1]))
Output:
(6,7,6)
None
It does not handle plateaus.
Doku:
- zip(), filter() and max()
answered Nov 16 '18 at 17:21
Patrick ArtnerPatrick Artner
26.6k62544
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
StackExchange.using("externalEditor", function () {
StackExchange.using("snippets", function () {
StackExchange.snippets.init();
});
});
}, "code-snippets");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "1"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f53342353%2fmaximum-number-in-mountain-sequence%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
this should be more efficient than your approach. it is a binary search customized for your use-case:
def top(lst):
low = 0
high = len(lst)
while low != high:
i = (high+low)//2
if lst[i] < lst[i+1]:
low = i+1
else:
high = i
return low
it starts in the middle of the list and checks if the series is still increasing there. if it is it sets low and will ignore all indices below low for the rest of the algorithm. if the series decreases already, high is set to the current index and all the elements above are ignored. and so on... when high == low the algorithm terminates.
if you have two or more of the same elements at the maximum of your list (a plateau) the algorithm will not even terminate.
and i skipped the tests for empty lists or lists of length 1.
answered Nov 16 '18 at 17:15
hiro protagonisthiro protagonist
20.7k74264
Thank you for your answer. I know the binary search solution. I just want to figure out what's wrong with my code. But thx!
– Wei Bovey
Nov 16 '18 at 19:11
you ignore the last element in your lastforloop... should berange(len(nums) - 1).
– hiro protagonist
Nov 16 '18 at 19:37
OMG! Gotcha! Thank you so much!
– Wei Bovey
Nov 18 '18 at 18:47
add a comment |
this should be more efficient than your approach. it is a binary search customized for your use-case:
def top(lst):
low = 0
high = len(lst)
while low != high:
i = (high+low)//2
if lst[i] < lst[i+1]:
low = i+1
else:
high = i
return low
it starts in the middle of the list and checks if the series is still increasing there. if it is it sets low and will ignore all indices below low for the rest of the algorithm. if the series decreases already, high is set to the current index and all the elements above are ignored. and so on... when high == low the algorithm terminates.
if you have two or more of the same elements at the maximum of your list (a plateau) the algorithm will not even terminate.
and i skipped the tests for empty lists or lists of length 1.
answered Nov 16 '18 at 17:15
hiro protagonisthiro protagonist
20.7k74264
Thank you for your answer. I know the binary search solution. I just want to figure out what's wrong with my code. But thx!
– Wei Bovey
Nov 16 '18 at 19:11
you ignore the last element in your lastforloop... should berange(len(nums) - 1).
– hiro protagonist
Nov 16 '18 at 19:37
OMG! Gotcha! Thank you so much!
– Wei Bovey
Nov 18 '18 at 18:47
add a comment |
this should be more efficient than your approach. it is a binary search customized for your use-case:
def top(lst):
low = 0
high = len(lst)
while low != high:
i = (high+low)//2
if lst[i] < lst[i+1]:
low = i+1
else:
high = i
return low
it starts in the middle of the list and checks if the series is still increasing there. if it is it sets low and will ignore all indices below low for the rest of the algorithm. if the series decreases already, high is set to the current index and all the elements above are ignored. and so on... when high == low the algorithm terminates.
if you have two or more of the same elements at the maximum of your list (a plateau) the algorithm will not even terminate.
and i skipped the tests for empty lists or lists of length 1.
answered Nov 16 '18 at 17:15
hiro protagonisthiro protagonist
20.7k74264
this should be more efficient than your approach. it is a binary search customized for your use-case:
def top(lst):
low = 0
high = len(lst)
while low != high:
i = (high+low)//2
if lst[i] < lst[i+1]:
low = i+1
else:
high = i
return low
it starts in the middle of the list and checks if the series is still increasing there. if it is it sets low and will ignore all indices below low for the rest of the algorithm. if the series decreases already, high is set to the current index and all the elements above are ignored. and so on... when high == low the algorithm terminates.
if you have two or more of the same elements at the maximum of your list (a plateau) the algorithm will not even terminate.
and i skipped the tests for empty lists or lists of length 1.
answered Nov 16 '18 at 17:15
hiro protagonisthiro protagonist
20.7k74264
edited Nov 16 '18 at 18:16
answered Nov 16 '18 at 17:15
hiro protagonisthiro protagonist
20.7k74264
answered Nov 16 '18 at 17:15
hiro protagonisthiro protagonist
20.7k74264
answered Nov 16 '18 at 17:15
hiro protagonisthiro protagonist
20.7k74264
20.7k74264
Thank you for your answer. I know the binary search solution. I just want to figure out what's wrong with my code. But thx!
– Wei Bovey
Nov 16 '18 at 19:11
you ignore the last element in your lastforloop... should berange(len(nums) - 1).
– hiro protagonist
Nov 16 '18 at 19:37
OMG! Gotcha! Thank you so much!
– Wei Bovey
Nov 18 '18 at 18:47
add a comment |
Thank you for your answer. I know the binary search solution. I just want to figure out what's wrong with my code. But thx!
– Wei Bovey
Nov 16 '18 at 19:11
you ignore the last element in your lastforloop... should berange(len(nums) - 1).
– hiro protagonist
Nov 16 '18 at 19:37
OMG! Gotcha! Thank you so much!
– Wei Bovey
Nov 18 '18 at 18:47
Thank you for your answer. I know the binary search solution. I just want to figure out what's wrong with my code. But thx!
– Wei Bovey
Nov 16 '18 at 19:11
Thank you for your answer. I know the binary search solution. I just want to figure out what's wrong with my code. But thx!
– Wei Bovey
Nov 16 '18 at 19:11
you ignore the last element in your last
for loop... should be range(len(nums) - 1) .– hiro protagonist
Nov 16 '18 at 19:37
you ignore the last element in your last
for loop... should be range(len(nums) - 1) .– hiro protagonist
Nov 16 '18 at 19:37
OMG! Gotcha! Thank you so much!
– Wei Bovey
Nov 18 '18 at 18:47
OMG! Gotcha! Thank you so much!
– Wei Bovey
Nov 18 '18 at 18:47
add a comment |
This will get all triplets from your input, isolate all that are higher in the middle then left or right and return the one that is highest overall:
def get_mountain_top(seq):
triplets = zip(seq, seq[1:], seq[2:])
tops = list(filter(lambda x: x[0] < x[1] > x[2], triplets))
if tops:
# max not allowed, leverage sorted
return sorted(tops, key = lambda x:x[1])[-1]
# return max(tops,key = lambda x:x[1])
return None
print(get_mountain_top([1,2,3,4,3,2,3,4,5,6,7,6,5]))
print(get_mountain_top([1,1,1]))
Output:
(6,7,6)
None
It does not handle plateaus.
Doku:
- zip(), filter() and max()
answered Nov 16 '18 at 17:21
Patrick ArtnerPatrick Artner
26.6k62544
add a comment |
This will get all triplets from your input, isolate all that are higher in the middle then left or right and return the one that is highest overall:
def get_mountain_top(seq):
triplets = zip(seq, seq[1:], seq[2:])
tops = list(filter(lambda x: x[0] < x[1] > x[2], triplets))
if tops:
# max not allowed, leverage sorted
return sorted(tops, key = lambda x:x[1])[-1]
# return max(tops,key = lambda x:x[1])
return None
print(get_mountain_top([1,2,3,4,3,2,3,4,5,6,7,6,5]))
print(get_mountain_top([1,1,1]))
Output:
(6,7,6)
None
It does not handle plateaus.
Doku:
- zip(), filter() and max()
answered Nov 16 '18 at 17:21
Patrick ArtnerPatrick Artner
26.6k62544
add a comment |
This will get all triplets from your input, isolate all that are higher in the middle then left or right and return the one that is highest overall:
def get_mountain_top(seq):
triplets = zip(seq, seq[1:], seq[2:])
tops = list(filter(lambda x: x[0] < x[1] > x[2], triplets))
if tops:
# max not allowed, leverage sorted
return sorted(tops, key = lambda x:x[1])[-1]
# return max(tops,key = lambda x:x[1])
return None
print(get_mountain_top([1,2,3,4,3,2,3,4,5,6,7,6,5]))
print(get_mountain_top([1,1,1]))
Output:
(6,7,6)
None
It does not handle plateaus.
Doku:
- zip(), filter() and max()
answered Nov 16 '18 at 17:21
Patrick ArtnerPatrick Artner
26.6k62544
This will get all triplets from your input, isolate all that are higher in the middle then left or right and return the one that is highest overall:
def get_mountain_top(seq):
triplets = zip(seq, seq[1:], seq[2:])
tops = list(filter(lambda x: x[0] < x[1] > x[2], triplets))
if tops:
# max not allowed, leverage sorted
return sorted(tops, key = lambda x:x[1])[-1]
# return max(tops,key = lambda x:x[1])
return None
print(get_mountain_top([1,2,3,4,3,2,3,4,5,6,7,6,5]))
print(get_mountain_top([1,1,1]))
Output:
(6,7,6)
None
It does not handle plateaus.
Doku:
- zip(), filter() and max()
answered Nov 16 '18 at 17:21
Patrick ArtnerPatrick Artner
26.6k62544
edited Nov 16 '18 at 17:28
answered Nov 16 '18 at 17:21
Patrick ArtnerPatrick Artner
26.6k62544
answered Nov 16 '18 at 17:21
Patrick ArtnerPatrick Artner
26.6k62544
answered Nov 16 '18 at 17:21
Patrick ArtnerPatrick Artner
26.6k62544
26.6k62544
add a comment |
add a comment |
Thanks for contributing an answer to Stack Overflow!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f53342353%2fmaximum-number-in-mountain-sequence%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
given you do not try a binary search (and maybe you should); why not just
max(nums)?– hiro protagonist
Nov 16 '18 at 17:05
10 is not a mountain - it does not increase beforehand only decrease after
– Patrick Artner
Nov 16 '18 at 17:09
what about plateaus:
7, 8, 9, 9, 9, 8, 7?– Patrick Artner
Nov 16 '18 at 17:11
actually its not allowed to use max(). I was just being lazy to write some more if. LOL
– Wei Bovey
Nov 16 '18 at 17:16
1
You're providing a wrong argument to the range function and the loop is missing one element. Change it for
range(len(nums) - 1).– fsinisi90
Nov 16 '18 at 17:24