Спиральный обход матрицы

Решение: Спиральный обход матрицы

Это задача требует обхода матрицы по спирали: слева направо, сверху вниз, справа налево, снизу вверх, и повторения этого процесса для внутренних слоёв матрицы. Используем подход с четырьмя указателями границ.

Алгоритм решения

1. Инициализируем четыре указателя для границ матрицы: top, bottom, left, right
2. Проходим спирально:
   • Слева направо по верхней строке (top)
   • Сверху вниз по правому столбцу (right)
   • Справа налево по нижней строке (bottom), если есть оставшиеся строки
   • Снизу вверх по левому столбцу (left), если есть оставшиеся столбцы
3. Сужаем границы после каждого прохода
4. Повторяем пока не обойдём всю матрицу

Визуализация

Матрица 3x3:
1 2 3
4 5 6
7 8 9

Шаг 1 - Слева направо по top: 1, 2, 3 (top--)
Шаг 2 - Сверху вниз по right: 6, 9 (right--)
Шаг 3 - Справа налево по bottom: 8, 7 (bottom--)
Шаг 4 - Снизу вверх по left: 4, 5 (left++)

Результат: [1, 2, 3, 6, 9, 8, 7, 4, 5]

Реализация решения

def spiralOrder(matrix):
    """
    Возвращает элементы матрицы в спиральном порядке.
    
    Args:
        matrix: Матрица M x N
    
    Returns:
        Список элементов в спиральном порядке
    """
    if not matrix or not matrix[0]:
        return []
    
    result = []
    top, bottom = 0, len(matrix) - 1
    left, right = 0, len(matrix[0]) - 1
    
    while top <= bottom and left <= right:
        # Слева направо по верхней строке
        for col in range(left, right + 1):
            result.append(matrix[top][col])
        top += 1
        
        # Сверху вниз по правому столбцу
        for row in range(top, bottom + 1):
            result.append(matrix[row][right])
        right -= 1
        
        # Справа налево по нижней строке (если есть)
        if top <= bottom:
            for col in range(right, left - 1, -1):
                result.append(matrix[bottom][col])
            bottom -= 1
        
        # Снизу вверх по левому столбцу (если есть)
        if left <= right:
            for row in range(bottom, top - 1, -1):
                result.append(matrix[row][left])
            left += 1
    
    return result

Пошаговый разбор примера

Вход: [[1,2,3],[4,5,6],[7,8,9]]

Инициализация:

top = 0, bottom = 2, left = 0, right = 2

Итерация 1:

Шаг 1 (слева направо, top=0): 1, 2, 3 (top=1)
Шаг 2 (сверху вниз, right=2): 6, 9 (right=1)
Шаг 3 (справа налево, bottom=2): 8, 7 (bottom=1)
Шаг 4 (снизу вверх, left=0): 4, 5 (left=1)

Итерация 2:

top=1, bottom=1, left=1, right=1
Средний элемент 5 уже обойдён
top > bottom → выход

Выход: [1, 2, 3, 6, 9, 8, 7, 4, 5] ✓

Обработка граничных случаев

def spiralOrder_safe(matrix):
    """
    Версия с обработкой граничных случаев
    """
    # Проверка на пустую матрицу
    if not matrix:
        return []
    if not matrix[0]:
        return []
    
    m, n = len(matrix), len(matrix[0])
    result = []
    
    top, bottom, left, right = 0, m - 1, 0, n - 1
    
    while top <= bottom and left <= right:
        # Проход слева направо
        for j in range(left, right + 1):
            result.append(matrix[top][j])
        top += 1
        
        # Проход сверху вниз
        for i in range(top, bottom + 1):
            result.append(matrix[i][right])
        right -= 1
        
        # Проход справа налево (только если есть строки)
        if top <= bottom:
            for j in range(right, left - 1, -1):
                result.append(matrix[bottom][j])
            bottom -= 1
        
        # Проход снизу вверх (только если есть столбцы)
        if left <= right:
            for i in range(bottom, top - 1, -1):
                result.append(matrix[i][left])
            left += 1
    
    return result

Тестовые случаи

# Основной пример
print(spiralOrder([[1,2,3],[4,5,6],[7,8,9]]))
# [1, 2, 3, 6, 9, 8, 7, 4, 5]

# Матрица 1x4 (одна строка)
print(spiralOrder([[1,2,3,4]]))
# [1, 2, 3, 4]

# Матрица 4x1 (один столбец)
print(spiralOrder([[1],[2],[3],[4]]))
# [1, 2, 3, 4]

# Матрица 1x1
print(spiralOrder([[5]]))
# [5]

# Матрица 2x2
print(spiralOrder([[1,2],[3,4]]))
# [1, 2, 4, 3]

# Матрица 2x3
print(spiralOrder([[1,2,3],[4,5,6]]))
# [1, 2, 3, 6, 5, 4]

# Матрица 3x2
print(spiralOrder([[1,2],[3,4],[5,6]]))
# [1, 2, 4, 6, 5, 3]

# Пустая матрица
print(spiralOrder([]))
# []

# Матрица с пустыми строками
print(spiralOrder([[], []]))
# []

Альтернативное решение с использованием поворота

def spiralOrder_rotate(matrix):
    """
    Рекурсивное решение с поворотом матрицы
    """
    if not matrix or not matrix[0]:
        return []
    
    # Первая строка + спираль оставшейся матрицы (повёрнутой)
    result = matrix[0]
    
    if len(matrix) > 1:
        # Проворачиваем оставшуюся матрицу на 90 градусов
        remaining = [[matrix[i][j] for i in range(len(matrix) - 1, 0, -1)] 
                     for j in range(1, len(matrix[0]))]
        
        result += spiralOrder_rotate(remaining)
    
    return result

Сложность

• Временная сложность: O(m * n), где m и n — размеры матрицы (посещаем каждый элемент один раз)
• Пространственная сложность: O(1), не считая выходного массива (используем только указатели)

Визуализация разных размеров матриц

Матрица 2x3:

1 2 3
4 5 6

Обход: 1 → 2 → 3 → 6 → 5 → 4

Матрица 4x4:

1  2  3  4
5  6  7  8
9  10 11 12
13 14 15 16

Обход: 1→2→3→4→8→12→16→15→14→13→9→5→6→7→11→10

Важные детали

• Проверка границ перед горизонтальными проходами справа налево и вертикальными проходами снизу вверх
• Уменьшение границ происходит после каждого прохода
• Граничные случаи включают матрицы из одной строки, одного столбца или одного элемента

Решение оптимально по времени и подходит для production-кода. Двухмерный обход требует внимательности, но алгоритм интуитивен после понимания основной идеи.