Longest Mountain in Array (M)
題目
Let's call any (contiguous) subarray B (of A) a mountain if the following properties hold:
B.length >= 3- There exists some
0 < i < B.length - 1such thatB[0] < B[1] < ... B[i-1] < B[i] > B[i+1] > ... > B[B.length - 1]
(Note that B could be any subarray of A, including the entire array A.)
Given an array A of integers, return the length of the longest mountain.
Return 0 if there is no mountain.
Example 1:
Input: [2,1,4,7,3,2,5]
Output: 5
Explanation: The largest mountain is [1,4,7,3,2] which has length 5.
Example 2:
Input: [2,2,2]
Output: 0
Explanation: There is no mountain.
Note:
0 <= A.length <= 100000 <= A[i] <= 10000
Follow up:
- Can you solve it using only one pass?
- Can you solve it in
O(1)space?
題意
陣列中，如果一個區間的左半部分嚴格單調遞增，右半部分嚴格單調遞減，將這個區間稱為一個“山”，要求在給定陣列中求這樣的區間的最大長度，
思路
用變數start、end分別表示這樣的區間的兩個端點，對于每一個start，找到能使區間成“山”的end值，計算長度，更新start并重復步驟，
代碼實作
Java
class Solution {
public int longestMountain(int[] A) {
int ans = 0;
int start = 0, end = 0;
while (start < A.length) {
if (end < A.length - 1 && A[end] < A[end + 1]) {
while (end < A.length - 1 && A[end] < A[end + 1]) {
end++;
}
if (end < A.length - 1 && A[end] > A[end + 1]) {
while (end < A.length - 1 && A[end] > A[end + 1]) {
end++;
}
ans = Math.max(ans, end - start + 1);
}
}
start = end > start ? end : start + 1;
end = start;
}
return ans;
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/220354.html
標籤：其他