1. topic
2. answers
2.1 method 1
The left array represents the number of elements smaller than the current element on the left side of the current element, and the right array represents the number of elements smaller than the current element on the right side of the current element. In the middle of the mountain, B[i], there must be elements smaller than B[i] on the left and right, and the length of the mountain is left[i] + right[i] + 1.
class Solution { public: int longestMountain(vector<int>& A) { int n = A.size(); if (n < 3) return 0; vector<int> left(n, 0); vector<int> right(n, 0); for (int i = 1; i < n; i++) { if (A[i] > A[i-1]) left[i] = left[i-1] + 1; } for (int i = n-2; i >= 0; i--) { if (A[i] > A[i+1]) right[i] = right[i+1] + 1;; } int len = 0; for (int i = 0; i < n; i++) { if (left[i] != 0 && right[i] != 0) len = max(len, left[i] + right[i] + 1); } return len; } };
2.2 method 2
If the array is 1, the current element is larger than the left element. If the array is 1, the current element is larger than the right element.
In the case of mountains, the two arrays should be in the following sequence
Array value | |||||
---|---|---|---|---|---|
max_than_left | 1 (optional) | ... | 1 (selected) | ... | 0 (optional) |
max_than_right | 0 (optional) | ... | 1 (selected) | ... | 1 (optional) |
class Solution { public: int longestMountain(vector<int>& A) { int n = A.size(); if (n < 3) return 0; vector<int> max_than_left(n, 0); vector<int> max_than_right(n, 0); for (int i = 1; i < n; i++) { if (A[i] > A[i-1]) max_than_left[i] = 1; } for (int i = 0; i < n-1; i++) { if (A[i] > A[i+1]) max_than_right[i] = 1; } int result = 0; int len = 0; int left_flag = 0; int middle_flag = 0; int right_flag = 0; for (int i = 0; i < n; i++) { if (max_than_left[i] == 1 && max_than_right[i] == 0) { if (left_flag) result++; else { result = 3; left_flag = 1; } } else if (max_than_left[i] == 1 && max_than_right[i] == 1) { if (left_flag) { result++; } else { result = 3; } left_flag = 0; middle_flag = 1; } else if (max_than_left[i] == 0 && max_than_right[i] == 1) { if (right_flag) result++; if (middle_flag) { middle_flag = 0; right_flag = 1; result++; } } else { right_flag = 0; middle_flag = 0; left_flag = 0; result = 0; } if (middle_flag || right_flag) len = max(len, result); } return len; } };
For more highlights, please pay attention to "seniusen"!