Sponsored
Sponsored
This approach involves scanning the array to find all the peaks and then measuring the length of a mountain centered at each peak. We use two traversals: one forward scan to detect peaks and another scan to calculate maximum width of the mountains.
Time complexity is O(n) as each element is processed at most twice. Space complexity is O(1) since we use only a few extra variables.
1#include <vector>
2#include <algorithm>
3using namespace std;
4
5int longestMountain(vector<int>& arr) {
6 int n = arr.size();
7 if (n < 3) return 0;
8 int maxLen = 0;
9 for (int i = 1; i < n - 1; ) {
10 if (arr[i] > arr[i - 1] && arr[i] > arr[i + 1]) {
11 int left = i, right = i;
12 while (left > 0 && arr[left] > arr[left - 1]) left--;
13 while (right < n - 1 && arr[right] > arr[right + 1]) right++;
14 maxLen = max(maxLen, right - left + 1);
15 i = right + 1;
16 } else {
17 i++;
18 }
19 }
20 return maxLen;
21}
22
23int main() {
24 vector<int> arr = {2, 1, 4, 7, 3, 2, 5};
25 printf("%d\n", longestMountain(arr));
26 return 0;
27}The C++ solution follows the same logic, utilizing standard libraries for vector manipulation. The code finds peaks and then determines the extent of the mountain using a left and right index, updating the maximum mountain length found so far.
This approach uses a single pass through the array to maintain both ascent and descent counts, swapping them at every ascent reset. A separate check is performed to ensure valid peaks for mountain length calculations.
Time complexity is O(n) for a single well-managed loop, with O(1) space thanks to a fixed set of variables.
1
JavaScript's style embraces a function-driven logic, following a singular indexing gesture to accomplish mountain recognition and calculate associated lengths when present.