PrepBro
← Назад к вопросам

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

1.0 Junior🔥 161 комментариев
#Python Core

Условие

Верните все элементы матрицы в порядке спирального обхода (по часовой стрелке, начиная с левого верхнего угла).

Пример

Вход:

[[1, 2, 3],
 [4, 5, 6],
 [7, 8, 9]]

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

Комментарии (1)

🐱
claude-haiku-4.5PrepBro AI23 мар. 2026 г.(ред.)

Ответ сгенерирован нейросетью и может содержать ошибки

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

Это классическая задача на обход матрицы. Требует аккуратной работы с границами и логикой направлений.

1. Анализ проблемы

Спиральный обход — движение по внешнему слою матрицы, потом по внутренним слоям.

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

Порядок обхода:
→ → ↓    (строка 0: 1, 2, 3)
    ↓    (столбец 2: 6, 9)
  ← ←    (строка 2: 8, 7)
↑        (столбец 0: 4)
↑        (центр: 5)

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

2. Решение 1: Четыре цикла направлений

def spiral_order(matrix: list[list[int]]) -> list[int]:
    """Спиральный обход с явными направлениями."""
    
    if not matrix:
        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

# Тестирование
matrix = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
print(spiral_order(matrix))  # [1, 2, 3, 6, 9, 8, 7, 4, 5]

Анализ:

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

Визуализация работы:

Матрица 3×3:
1  2  3    top=0, bottom=2, left=0, right=2
4  5  6
7  8  9

Шаг 1 (top <= bottom && left <= right):
  Вправо (col 0→2, row 0): 1, 2, 3    top=1
  Вниз (row 1→2, col 2): 6, 9           right=1
  Влево (col 1→0, row 2): 8, 7          bottom=1
  Вверх (row 1→1, col 0): 4             left=1

Шаг 2 (top <= bottom && left <= right):
  top=1, bottom=1, left=1, right=1
  Вправо (col 1→1, row 1): 5            top=2
  Цикл завершен (top > bottom)

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

3. Решение 2: Направления с дельтами

def spiral_order_directions(matrix: list[list[int]]) -> list[int]:
    """Спиральный обход с использованием направлений."""
    
    if not matrix:
        return []
    
    m, n = len(matrix), len(matrix[0])
    result = []
    visited = [[False] * n for _ in range(m)]
    
    # Направления: вправо, вниз, влево, вверх
    directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
    direction_idx = 0
    row, col = 0, 0
    
    for _ in range(m * n):
        result.append(matrix[row][col])
        visited[row][col] = True
        
        # Пытаемся продолжить в текущем направлении
        dr, dc = directions[direction_idx]
        next_row, next_col = row + dr, col + dc
        
        # Если выходим за границы или уже посещали — меняем направление
        if not (0 <= next_row < m and 0 <= next_col < n and not visited[next_row][next_col]):
            direction_idx = (direction_idx + 1) % 4
            dr, dc = directions[direction_idx]
            next_row, next_col = row + dr, col + dc
        
        row, col = next_row, next_col
    
    return result

Преимущество: Более гибкий для других видов спирального обхода.

4. Полная реализация с тестами

from typing import List
import unittest

class Solution:
    @staticmethod
    def spiral_order(matrix: List[List[int]]) -> List[int]:
        """Оптимальное решение."""
        if not matrix:
            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


class TestSpiralOrder(unittest.TestCase):
    
    def test_3x3_matrix(self):
        """Стандартный пример 3×3."""
        matrix = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
        expected = [1, 2, 3, 6, 9, 8, 7, 4, 5]
        self.assertEqual(Solution.spiral_order(matrix), expected)
    
    def test_1x1_matrix(self):
        """Матрица 1×1."""
        matrix = [[1]]
        expected = [1]
        self.assertEqual(Solution.spiral_order(matrix), expected)
    
    def test_1xn_matrix(self):
        """Матрица 1×n (одна строка)."""
        matrix = [[1, 2, 3, 4]]
        expected = [1, 2, 3, 4]
        self.assertEqual(Solution.spiral_order(matrix), expected)
    
    def test_mx1_matrix(self):
        """Матрица m×1 (один столбец)."""
        matrix = [[1], [2], [3], [4]]
        expected = [1, 2, 3, 4]
        self.assertEqual(Solution.spiral_order(matrix), expected)
    
    def test_2x2_matrix(self):
        """Матрица 2×2."""
        matrix = [[1, 2], [3, 4]]
        expected = [1, 2, 4, 3]
        self.assertEqual(Solution.spiral_order(matrix), expected)
    
    def test_4x4_matrix(self):
        """Матрица 4×4."""
        matrix = [
            [1, 2, 3, 4],
            [5, 6, 7, 8],
            [9, 10, 11, 12],
            [13, 14, 15, 16]
        ]
        expected = [1, 2, 3, 4, 8, 12, 16, 15, 14, 13, 9, 5, 6, 7, 11, 10]
        self.assertEqual(Solution.spiral_order(matrix), expected)
    
    def test_3x4_matrix(self):
        """Матрица 3×4 (не квадратная)."""
        matrix = [
            [1, 2, 3, 4],
            [5, 6, 7, 8],
            [9, 10, 11, 12]
        ]
        expected = [1, 2, 3, 4, 8, 12, 11, 10, 9, 5, 6, 7]
        self.assertEqual(Solution.spiral_order(matrix), expected)
    
    def test_empty_matrix(self):
        """Пустая матрица."""
        matrix = []
        expected = []
        self.assertEqual(Solution.spiral_order(matrix), expected)

if __name__ == '__main__':
    unittest.main()

5. Граничные случаи

Случай 1: Одна строка
[1, 2, 3, 4]
→ [1, 2, 3, 4]

Случай 2: Один столбец
[1]
[2]
[3]
[4]
↓ [1, 2, 3, 4]

Случай 3: Две строки и два столбца
[1, 2]
[3, 4]
→ ↓    [1, 2, 4, 3]
  ←
  ↑

Случай 4: Две строки и три столбца
[1, 2, 3]
[4, 5, 6]
→ → →    [1, 2, 3, 6, 5, 4]
        ↓
    ← ←

6. Визуализация сложной матрицы 5×5

 1  2  3  4  5
 6  7  8  9 10
11 12 13 14 15
16 17 18 19 20
21 22 23 24 25

Спиральный порядок:
Внешний слой: 1, 2, 3, 4, 5, 10, 15, 20, 25, 24, 23, 22, 21, 16, 11, 6
Второй слой:  7, 8, 9, 14, 19, 18, 17, 12
Третий слой:  13

Результат: [1, 2, 3, 4, 5, 10, 15, 20, 25, 24, 23, 22, 21, 16, 11, 6, 7, 8, 9, 14, 19, 18, 17, 12, 13]

7. Обратное преобразование: расположение элемента в спирали

def spiral_position(m: int, n: int, target: int) -> tuple:
    """Найти позицию элемента в спиральном порядке."""
    result = []
    top, bottom = 0, m - 1
    left, right = 0, n - 1
    position = 0
    
    while top <= bottom and left <= right:
        for col in range(left, right + 1):
            if position == target:
                return (top, col)
            position += 1
        top += 1
        
        for row in range(top, bottom + 1):
            if position == target:
                return (row, right)
            position += 1
        right -= 1
        
        if top <= bottom:
            for col in range(right, left - 1, -1):
                if position == target:
                    return (bottom, col)
                position += 1
            bottom -= 1
        
        if left <= right:
            for row in range(bottom, top - 1, -1):
                if position == target:
                    return (row, left)
                position += 1
            left += 1
    
    return (-1, -1)  # Не найдено

8. Сравнение подходов

ПодходВремениПамятьСложностьГибкость
Четыре циклаO(m×n)O(1)СредняяНизкая
С направлениямиO(m×n)O(m×n)ВысокаяВысокая

9. Альтернативный обход — против часовой стрелки

def spiral_order_ccw(matrix: List[List[int]]) -> List[int]:
    """Спиральный обход против часовой стрелки."""
    if not matrix:
        return []
    
    result = []
    top, bottom = 0, len(matrix) - 1
    left, right = 0, len(matrix[0]) - 1
    
    while top <= bottom and left <= right:
        # Вниз (левый столбец)
        for row in range(top, bottom + 1):
            result.append(matrix[row][left])
        left += 1
        
        # Вправо (нижняя строка)
        for col in range(left, right + 1):
            result.append(matrix[bottom][col])
        bottom -= 1
        
        # Вверх (правый столбец)
        if left <= right:
            for row in range(bottom, top - 1, -1):
                result.append(matrix[row][right])
            right -= 1
        
        # Влево (верхняя строка)
        if top <= bottom:
            for col in range(right, left - 1, -1):
                result.append(matrix[top][col])
            top += 1
    
    return result

Вывод

Для спирального обхода матрицы:

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

Частая задача на собеседованиях — проверяет аккуратность работы с индексами и логику алгоритма.

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