896. Monotonic Array

Задача

Массив является монотонным, если он либо монотонно возрастает, либо монотонно убывает.

Массив nums является монотонно возрастающим, если для всех i <= j выполняется nums[i] <= nums[j] . Массив nums является монотонно убывающим, если для всех i <= j выполняется nums[i] >= nums[j] .

Дан целочисленный массив nums , верните true , если данный массив является монотонным, или false в противном случае.

Примеры

Пример 1

Input: nums = [1,2,2,3]
Output: true

Пример 2

Input: nums = [6,5,4,4]
Output: true

Пример 3

Input: nums = [1,3,2]
Output: false

Решение

Решение

/**
 * Временная сложность: O(N)
 * Пространственная сложность: O(1)
 */
var isMonotonic = function(nums) {
    let isIncreasing = true;
    let isDecreasing = true;
 
    for (let i = 0; i < nums.length - 1; i++) {
        // Если встретили убывание, значит это не может быть возрастающий массив
        if (nums[i] > nums[i + 1]) {
            isIncreasing = false;
        }
 
        // Если встретили возрастание, значит это не может быть убывающий массив
        if (nums[i] < nums[i + 1]) {
            isDecreasing = false;
        }
 
        // Оптимизация: Если оба флага стали false, можно выходить досрочно
        if (!isIncreasing && !isDecreasing) {
            return false;
        }
    }
 
    // Если хотя бы один флаг остался true — массив монотонный
    return isIncreasing || isDecreasing;
};

Решение 2

/**
 * Временная сложность: O(N)
 * Пространственная сложность: O(1)
 */
var isMonotonic = function(nums) {
    let direction = 0; // 0 - направление пока неизвестно
 
    for (let i = 0; i < nums.length - 1; i++) {
        const diff = nums[i + 1] - nums[i];
 
        if (diff === 0) continue; // Пропускаем равные элементы
 
        if (direction === 0) {
            // Если направление еще не задано, задаем его
            direction = diff > 0 ? 1 : -1;
        } else {
            // Если направление уже есть, проверяем, не нарушается ли оно
            // Если direction = 1, а diff < 0 (или наоборот) — это ошибка
            if ((direction > 0 && diff < 0) || (direction < 0 && diff > 0)) {
                return false;
            }
        }
    }
 
    return true;
};