Чем проще, тем лучше!

В этом уроке ты

Научишься решать задачи, где важно искать максимально простое решение, не усложняя код.
Потренируешься на задаче с реального собеседования в BigTech.

Пример задачи с собеседования

Представь, что ты на собеседовании. Для разминки интервьюер даёт тебе простую задачу:

Условие

Дан целочисленный массив nums. Нужно вернуть true, если массив монотонный, и false в обратном случае.

Массив считается монотонным, если он отсортирован (по возрастанию или убыванию).

Пример 1

Ввод: nums = [1,2,2,3]
Вывод: true

Пример 2

Ввод: nums = [5,4,-10]
Вывод: true

Пример 3

Ввод: nums = [5,4,1,2]
Вывод: false

В чем сложность задачи?

Основная ошибка — пытаться проверять монотонное возрастание и убывание по отдельности. Это усложняет код и увеличивает вероятность ошибки.

using System;
using System.Collections.Generic;

public class Solution
{
    // Время: O(n), где n - длина массива nums
    // Память: O(1)
    public static bool IsMonotonic(List<int> nums)
    {
        if (nums.Count <= 2)
        {
            return true;
        }

        int direction = 0; // 0 - неизвестный тип, 1 - возрастание, -1 - убывание

        for (int i = 1; i < nums.Count; i++)
        {
            if (nums[i] > nums[i - 1]) // возрастание
            {
                if (direction == 0)
                {
                    direction = 1;
                }
                else if (direction == -1)
                {
                    return false;
                }
            }
            else if (nums[i] < nums[i - 1]) // убывание
            {
                if (direction == 0)
                {
                    direction = -1;
                }
                else if (direction == 1)
                {
                    return false;
                }
            }
        }
        return true;
    }
}

#include <vector>

using namespace std;

// Время: O(n), где n - длина массива nums
// Память: O(1)
bool isMonotonic(vector<int>& nums) {
    if (nums.size() <= 2) {
        return true;
    }

    int direction = 0; // 0 - неизвестный тип, 1 - возрастание, -1 - убывание

    for (size_t i = 1; i < nums.size(); ++i) {
        if (nums[i] > nums[i - 1]) { // возрастание
            if (direction == 0) {
                direction = 1;
            } else if (direction == -1) {
                return false;
            }
        } else if (nums[i] < nums[i - 1]) { // убывание
            if (direction == 0) {
                direction = -1;
            } else if (direction == 1) {
                return false;
            }
        }
    }
    return true;
}

package main

import "fmt"

// Время: O(n), где n - длина массива nums
// Память: O(1)
func isMonotonic(nums []int) bool {
    if len(nums) <= 2 {
        return true
    }

    direction := 0 // 0 - неизвестный тип, 1 - возрастание, -1 - убывание

    for i := 1; i < len(nums); i++ {
        if nums[i] > nums[i-1] { // возрастание
            if direction == 0 {
                direction = 1
            } else if direction == -1 {
                return false
            }
        } else if nums[i] < nums[i-1] { // убывание
            if direction == 0 {
                direction = -1
            } else if direction == 1 {
                return false
            }
        }
    }
    return true
}

import java.util.List;

public class Monotonic {

    // Время: O(n), где n - длина массива nums
    // Память: O(1)
    public static boolean isMonotonic(List<Integer> nums) {
        if (nums.size() <= 2) {
            return true;
        }
        
        int direction = 0; // 0 - неизвестный тип, 1 - возрастание, -1 - убывание
        
        for (int i = 1; i < nums.size(); i++) {
            if (nums.get(i) > nums.get(i - 1)) { // возрастание
                if (direction == 0) {
                    direction = 1;
                } else if (direction == -1) {
                    return false;
                }
            } else if (nums.get(i) < nums.get(i - 1)) { // убывание
                if (direction == 0) {
                    direction = -1;
                } else if (direction == 1) {
                    return false;
                }
            }
        }
        return true;
    }
}

from typing import *

# Время: O(n), где n - длина массива nums
# Память: O(1)
def is_monotonic(nums: List[int]) -> bool:
    if len(nums)<= 2:
        return True
    direction = 0 # 0 - неизвестный тип, 1 - возрастание, 2 - убывание
        
    for i in range(1,len(nums)):
        if nums[i] > nums[i - 1]: # возрастание
            if direction == 0:
                direction = 1
            elif direction == -1:
                return False
        elif nums[i] < nums[i - 1]: # убывание
            if direction == 0:
                direction = -1
            elif direction == 1:
                return False
    return True

// Время: O(n), где n - длина массива nums
// Память: O(1)
function isMonotonic(nums) {
    if (nums.length <= 2) {
        return true;
    }

    let direction = 0; // 0 - неизвестный тип, 1 - возрастание, -1 - убывание

    for (let i = 1; i < nums.length; i++) {
        if (nums[i] > nums[i - 1]) { // возрастание
            if (direction === 0) {
                direction = 1;
            } else if (direction === -1) {
                return false;
            }
        } else if (nums[i] < nums[i - 1]) { // убывание
            if (direction === 0) {
                direction = -1;
            } else if (direction === 1) {
                return false;
            }
        }
    }
    
    return true;
}

Решение является оптимальным, но его сложно понять. Такое решение допустимо, однако велика вероятность, что ты сам можешь в нем допустить ошибку.

Как решить эффективно?

Основная идея решения задачи состоит в том, что нам не важно монотонно возрастает массив или монотонно убывает. Достаточно завести 2 флага, на монотонное возрастание и на монотонное убывание:

using System;
using System.Collections.Generic;

public class Solution
{
    public static bool IsMonotonic(List<int> nums)
    {
        bool isInc = true;
        bool isDec = true;

        for (int i = 1; i < nums.Count; i++)
        {
            isInc = isInc && nums[i - 1] <= nums[i];
            isDec = isDec && nums[i - 1] >= nums[i];
        }

        return isInc || isDec;
    }
}

#include <vector>

using namespace std;

bool isMonotonic(vector<int>& nums) {
    bool isInc = true;
    bool isDec = true;

    for (int i = 1; i < nums.size(); i++) {
        isInc = isInc && nums[i - 1] <= nums[i];
        isDec = isDec && nums[i - 1] >= nums[i];
    }

    return isInc || isDec;
}

package main

func isMonotonic(nums []int) bool {
    isInc := true
    isDec := true

    for i := 1; i < len(nums); i++ {
        isInc = isInc && nums[i-1] <= nums[i]
        isDec = isDec && nums[i-1] >= nums[i]
    }

    return isInc || isDec
}

import java.util.List;

public class Solution {
    public boolean isMonotonic(List<Integer> nums) {
        boolean isInc = true;
        boolean isDec = true;

        for (int i = 1; i < nums.size(); i++) {
            isInc = isInc && nums.get(i - 1) <= nums.get(i);
            isDec = isDec && nums.get(i - 1) >= nums.get(i);
        }

        return isInc || isDec;
    }
}

def is_monotonic(nums: List[int]) -> bool:
    is_inc = True
    is_dec = True
    for i in range(1, len(nums)):
        is_inc = is_inc and nums[i - 1] <= nums[i]
        is_dec = is_dec and nums[i - 1] >= nums[i]
    return is_inc or is_dec

export function isMonotonic(nums) {
    let isInc = true;
    let isDec = true;

    for (let i = 1; i < nums.length; i++) {
        isInc = isInc && nums[i - 1] <= nums[i];
        isDec = isDec && nums[i - 1] >= nums[i];
    }

    return isInc || isDec;
}

Мы решили выделить память для дополнительной переменной, и это дало нам возможность достичь ясного решения. Пусть переменных стало больше, читаемость кода того стоит.

Оценка по времени и памяти

Время: O(n), где n - размер nums
Память: O(1)

По времени у нас один проход по массиву. А по памяти мы используем два флага(is_dec и is_inc), поэтому дополнительная память — константа.

Паттерн "Чем проще тем лучше":

Иногда мы сами усложняем себе жизнь. Поэтому, выбирая из нескольких вариантов решений, стоит отдать предпочтение самому лаконичному, чтобы избежать ошибок.

Что дальше

Переходи к практическим задачам, чтобы закрепить новые знания.