<reponame>wangkuntian/leetcode
#!/usr/bin/env python
# -*- coding: utf-8 -*-

"""
__project__ =  'leetcode'
__file__    =  '__init__.py'
__author__  =  'king'
__time__    =  '2020/1/9 14:11'


                              _ooOoo_
                             o8888888o
                             88" . "88
                             (| -_- |)
                             O\  =  /O
                          ____/`---'\____
                        .'  \\|     |//  `.
                       /  \\|||  :  |||//  \
                      /  _||||| -:- |||||-  \
                      |   | \\\  -  /// |   |
                      | \_|  ''\---/''  |   |
                      \  .-\__  `-`  ___/-. /
                    ___`. .'  /--.--\  `. . __
                 ."" '<  `.___\_<|>_/___.'  >'"".
                | | :  `- \`.;`\ _ /`;.`/ - ` : | |
                \  \ `-.   \_ __\ /__ _/   .-` /  /
           ======`-.____`-.___\_____/___.-`____.-'======
                              `=---='
          ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
                       佛祖保佑        永无BUG
"""

"""
难度：中等

峰值元素是指其值大于左右相邻值的元素。

给定一个输入数组nums，其中 nums[i] ≠ nums[i+1]，找到峰值元素并返回其索引。

数组可能包含多个峰值，在这种情况下，返回任何一个峰值所在位置即可。

你可以假设nums[-1] = nums[n] = -∞。

示例 1:
输入: nums = [1,2,3,1]
输出: 2
解释: 3 是峰值元素，你的函数应该返回其索引 2。

示例2:
输入: nums = [1,2,1,3,5,6,4]
输出: 1 或 5
解释: 你的函数可以返回索引 1，其峰值元素为 2；
    或者返回索引 5， 其峰值元素为 6。

说明:
你的解法应该是O(logN)时间复杂度的。
"""


class Solution(object):
    def findPeakElement(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        for index in range(len(nums) - 1):
            if nums[index] > nums[index + 1]:
                return index
        return len(nums) - 1

    def findPeakElement_2(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        left = 0
        right = len(nums) - 1

        while left < right:
            mid = (left + right) // 2
            if nums[mid] > nums[mid + 1]:
                right = mid
            else:
                left = mid + 1
        return right


print(Solution().findPeakElement([1, 2, 3, 4]))
print(Solution().findPeakElement_2([4, 5, 6, 7, 1, 2, 3]))

#!/usr/bin/env python
# -*- coding: utf-8 -*-

"""
__project__ =  'leetcode'
__file__    =  '__init__.py'
__author__  =  'king'
__time__    =  '2020/1/9 14:11'


                              _ooOoo_
                             o8888888o
                             88" . "88
                             (| -_- |)
                             O\  =  /O
                          ____/`---'\____
                        .'  \\|     |//  `.
                       /  \\|||  :  |||//  \
                      /  _||||| -:- |||||-  \
                      |   | \\\  -  /// |   |
                      | \_|  ''\---/''  |   |
                      \  .-\__  `-`  ___/-. /
                    ___`. .'  /--.--\  `. . __
                 ."" '<  `.___\_<|>_/___.'  >'"".
                | | :  `- \`.;`\ _ /`;.`/ - ` : | |
                \  \ `-.   \_ __\ /__ _/   .-` /  /
           ======`-.____`-.___\_____/___.-`____.-'======
                              `=---='
          ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
                       佛祖保佑        永无BUG
"""

"""
难度：中等

峰值元素是指其值大于左右相邻值的元素。

给定一个输入数组nums，其中 nums[i] ≠ nums[i+1]，找到峰值元素并返回其索引。

数组可能包含多个峰值，在这种情况下，返回任何一个峰值所在位置即可。

你可以假设nums[-1] = nums[n] = -∞。

示例 1:
输入: nums = [1,2,3,1]
输出: 2
解释: 3 是峰值元素，你的函数应该返回其索引 2。

示例2:
输入: nums = [1,2,1,3,5,6,4]
输出: 1 或 5
解释: 你的函数可以返回索引 1，其峰值元素为 2；
    或者返回索引 5， 其峰值元素为 6。

说明:
你的解法应该是O(logN)时间复杂度的。
"""


class Solution(object):
    def findPeakElement(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        for index in range(len(nums) - 1):
            if nums[index] > nums[index + 1]:
                return index
        return len(nums) - 1

    def findPeakElement_2(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        left = 0
        right = len(nums) - 1

        while left < right:
            mid = (left + right) // 2
            if nums[mid] > nums[mid + 1]:
                right = mid
            else:
                left = mid + 1
        return right


print(Solution().findPeakElement([1, 2, 3, 4]))
print(Solution().findPeakElement_2([4, 5, 6, 7, 1, 2, 3]))
#!/usr/bin/env python # -*- coding: utf-8 -*- __project__ =  'leetcode' __file__    =  '__init__.py' __author__  =  'king' __time__    =  '2020/1/9 14:11'                                 _ooOoo_                              o8888888o                              88" . "88                              (| -_- |)                              O\  =  /O                           ____/`---'\____                         .'  \\|     |//  `.                        /  \\|||  :  |||//  \                       /  _||||| -:- |||||-  \                       |   | \\\  -  /// |   |                       | \_|  ''\---/''  |   |                       \  .-\__  `-`  ___/-. /                     ___`. .'  /--.--\  `. . __                  ."" '<  `.___\_<|>_/___.'  >'"".                 | | :  `- \`.;`\ _ /`;.`/ - ` : | |                 \  \ `-.   \_ __\ /__ _/   .-` /  /            ======`-.____`-.___\_____/___.-`____.-'======                               `=---='           ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^                        佛祖保佑        永无BUG 难度：中等  峰值元素是指其值大于左右相邻值的元素。  给定一个输入数组nums，其中 nums[i] ≠ nums[i+1]，找到峰值元素并返回其索引。  数组可能包含多个峰值，在这种情况下，返回任何一个峰值所在位置即可。  你可以假设nums[-1] = nums[n] = -∞。  示例 1: 输入: nums = [1,2,3,1] 输出: 2 解释: 3 是峰值元素，你的函数应该返回其索引 2。  示例2: 输入: nums = [1,2,1,3,5,6,4] 输出: 1 或 5 解释: 你的函数可以返回索引 1，其峰值元素为 2；     或者返回索引 5， 其峰值元素为 6。  说明: 你的解法应该是O(logN)时间复杂度的。 :type nums: List[int]         :rtype: int :type nums: List[int]         :rtype: int