845. Longest Mountain in Array

LeetCode medium оригинал: C# #array #csharp #leetcode #math #medium
LeetCode Static

Вы можете вспомнить, что массив arr является горным массивом тогда и только тогда, когда:

длина массива arr >= 3

Существует индекс i (счёт начинается с 0) такой, что:

arr[0] < arr[1] < ... < arr[i - 1] < arr[i]

arr[i] > arr[i + 1] > ... > arr[arr.length - 1]

Дан целочисленный массив arr, верните длину самой длинной подпоследовательности, которая является горной. Верните 0, если такой подпоследовательности нет.

Пример:

Input: arr = [2,1,4,7,3,2,5]

Output: 5

Explanation: The largest mountain is [1,4,7,3,2] which has length 5.

C# решение

сопоставлено/оригинал 
public class Solution {
    public int LongestMountain(int[] arr) {
        int n = arr.Length;
        int ans = 0;
        int baseIndex = 0;
        while (baseIndex < n) {
            int end = baseIndex;
            if (end + 1 < n && arr[end] < arr[end + 1]) {
                while (end + 1 < n && arr[end] < arr[end + 1]) {
                    end++;
                }
                if (end + 1 < n && arr[end] > arr[end + 1]) {
                    while (end + 1 < n && arr[end] > arr[end + 1]) {
                        end++;
                    }
                    ans = Math.Max(ans, end - baseIndex + 1);
                }
            }
            baseIndex = Math.Max(end, baseIndex + 1);
        }
        return ans;
    }
}

C++ решение

auto-draft, проверить перед отправкой 
#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public int LongestMountain(vector<int>& arr) {
        int n = arr.size();
        int ans = 0;
        int baseIndex = 0;
        while (baseIndex < n) {
            int end = baseIndex;
            if (end + 1 < n && arr[end] < arr[end + 1]) {
                while (end + 1 < n && arr[end] < arr[end + 1]) {
                    end++;
                }
                if (end + 1 < n && arr[end] > arr[end + 1]) {
                    while (end + 1 < n && arr[end] > arr[end + 1]) {
                        end++;
                    }
                    ans = max(ans, end - baseIndex + 1);
                }
            }
            baseIndex = max(end, baseIndex + 1);
        }
        return ans;
    }
}

Java решение

сопоставлено/оригинал 
class Solution {
    public int longestMountain(int[] A) {
        int N = A.length;
        int ans = 0, base = 0;
        while (base < N) {
            int end = base;
            if (end + 1 < N && A[end] < A[end + 1]) {
                while (end + 1 < N && A[end] < A[end + 1]) end++;

                if (end + 1 < N && A[end] > A[end + 1]) {
                    while (end + 1 < N && A[end] > A[end + 1]) end++;
                    ans = Math.max(ans, end - base + 1);
                }
            }

            base = Math.max(end, base + 1);
        }

        return ans;
    }
}

Python решение

сопоставлено/оригинал 
class Solution:
    def longestMountain(self, arr: List[int]) -> int:
        n = len(arr)
        ans = 0
        base = 0

        while base < n:
            end = base
            if end + 1 < n and arr[end] < arr[end + 1]:
                while end + 1 < n and arr[end] < arr[end + 1]:
                    end += 1
                if end + 1 < n and arr[end] > arr[end + 1]:
                    while end + 1 < n and arr[end] > arr[end + 1]:
                        end += 1
                    ans = max(ans, end - base + 1)
            base = max(end, base + 1)

        return ans

Go решение

сопоставлено/оригинал 
func longestMountain(arr []int) int {
    n := len(arr)
    ans := 0
    base := 0

    for base < n {
        end := base
        if end+1 < n && arr[end] < arr[end+1] {
            for end+1 < n && arr[end] < arr[end+1] {
                end++
            }
            if end+1 < n && arr[end] > arr[end+1] {
                for end+1 < n && arr[end] > arr[end+1] {
                    end++
                }
                ans = max(ans, end-base+1)
            }
        }
        base = max(end, base+1)
    }

    return ans
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

Algorithm

Инициализируйте переменные для отслеживания текущего основания и максимальной длины горного массива.

Для каждого индекса, который может быть началом горного массива, определите пиковый элемент и найдите правую границу горного массива.

Если найден горный массив, обновите максимальную длину и переместите основание на конец текущего горного массива.

😎

Вакансии для этой задачи

Показаны активные вакансии с пересечением по тегам задачи.

Все вакансии
Активных вакансий пока нет.