Java

  • /**
    
     852. Peak Index in a Mountain Array
    
     Let's call an array A a mountain if the following properties hold:
    
     A.length >= 3
     There exists some 0 < i < A.length - 1 such that A[0] < A[1] < ... A[i-1] < A[i] > A[i+1] > ... > A[A.length - 1]
     Given an array that is definitely a mountain, return any i such that A[0] < A[1] < ... A[i-1] < A[i] > A[i+1] > ... > A[A.length - 1].
    
     Example 1:
    
     Input: [0,1,0]
     Output: 1
     Example 2:
    
     Input: [0,2,1,0]
     Output: 1
     Note:
    
     3 <= A.length <= 10000
     0 <= A[i] <= 10^6
     A is a mountain, as defined above.
    
     @tag-array
    
     */
    
    public class Peak_Index_in_a_Mountain_Array {
    
        class Solution {
            public int peakIndexInMountainArray(int[] A) {
                int i = 0;
                while (A[i] < A[i+1]) {
                    i++;
                }
                return i;
            }
        }
    
        class Solution_BinarySearch {
            public int peakIndexInMountainArray(int[] A) {
    
                if (A == null || A.length == 0) {
                    return 0;
                }
    
                int i = 0;
                int j = A.length - 1;
    
                while (i < j) {
                    int mid = (i + j) / 2;
    
                    if (mid + 1 < A.length && A[mid + 1] > A[mid]) {
                        i = mid + 1;
                    }
                    else if (mid + 1 < A.length && A[mid + 1] < A[mid]) {
                        j = mid;
                    }
                    else if (mid + 1 < A.length && A[mid - 1] == A[mid]) {
                        i++;
                    }
                }
    
                return i;
            }
        }
    }
    
  • // OJ: https://leetcode.com/problems/peak-index-in-a-mountain-array/
    // Time: O(N)
    // Space: O(1)
    class Solution {
    public:
        int peakIndexInMountainArray(vector<int>& A) {
            int i = 1;
            while (i < A.size() && A[i] > A[i - 1]) ++i;
            return i - 1;
        }
    };
    
  • class Solution(object):
        def peakIndexInMountainArray(self, A):
            """
            :type A: List[int]
            :rtype: int
            """
            left, right = 0, len(A) - 1
            while left < right:
                mid = (left + right) / 2
                if A[mid - 1] < A[mid] and A[mid] < A[mid + 1]:
                    left = mid
                elif A[mid - 1] > A[mid] and A[mid] > A[mid + 1]:
                    right = mid
                else:
                    break
            return mid
    

Java

  • class Solution {
        public int peakIndexInMountainArray(int[] A) {
            int length = A.length;
            for (int i = 1; i < length; i++) {
                if (A[i] < A[i - 1])
                    return i - 1;
            }
            return -1;
        }
    }
    
  • // OJ: https://leetcode.com/problems/peak-index-in-a-mountain-array/
    // Time: O(N)
    // Space: O(1)
    class Solution {
    public:
        int peakIndexInMountainArray(vector<int>& A) {
            int i = 1;
            while (i < A.size() && A[i] > A[i - 1]) ++i;
            return i - 1;
        }
    };
    
  • class Solution(object):
        def peakIndexInMountainArray(self, A):
            """
            :type A: List[int]
            :rtype: int
            """
            left, right = 0, len(A) - 1
            while left < right:
                mid = (left + right) / 2
                if A[mid - 1] < A[mid] and A[mid] < A[mid + 1]:
                    left = mid
                elif A[mid - 1] > A[mid] and A[mid] > A[mid + 1]:
                    right = mid
                else:
                    break
            return mid
    

All Problems

All Solutions