Алгоритмы - Матрицы

Функция maximalRectangle находит площадь наибольшего прямоугольника, состоящего из единиц, в бинарной матрице.

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

Преобразование задачи в серию задач поиска наибольшей площади гистограммы
Построение гистограммы для каждой строки матрицы
Использование алгоритма поиска наибольшей площади гистограммы для каждой построенной гистограммы
Обновление максимальной найденной площади

Функция maximalRectangle:
- Проверяет входные данные на корректность
- Инициализирует массив высот гистограммы
- Итерируется по строкам матрицы, обновляя гистограмму
- Вызывает функцию largestRectangleArea для каждой гистограммы
Функция largestRectangleArea:
- Использует стек для эффективного поиска наибольшей площади в гистограмме
- Обрабатывает каждый столбец гистограммы, вычисляя возможные прямоугольники

Временная сложность: O(rows * cols), где rows и cols - размеры матрицы
- Каждый элемент матрицы обрабатывается один раз
- Для каждой строки выполняется линейный проход по гистограмме
Пространственная сложность: O(cols)
- Используется дополнительная память для хранения гистограммы
- Стек в худшем случае может содержать все столбцы

func maximalRectangle(matrix [][]byte) int {
	if len(matrix) == 0 || len(matrix[0]) == 0 {
		return 0
	}

	rows, cols := len(matrix), len(matrix[0])
	heights := make([]int, cols)
	maxArea := 0

	for i := 0; i < rows; i++ {
		for j := 0; j < cols; j++ {
			if matrix[i][j] == '1' {
				heights[j]++
			} else {
				heights[j] = 0
			}
		}
		area := largestRectangleArea(heights)
		if area > maxArea {
			maxArea = area
		}
	}

	return maxArea
}

func largestRectangleArea(heights []int) int {
	stack := []int{}
	maxArea := 0
	heights = append(heights, 0) // добавляем 0 в конец для обработки оставшихся элементов в стеке

	for i := 0; i <= len(heights)-1; i++ {
		for len(stack) > 0 && heights[stack[len(stack)-1]] > heights[i] {
			height := heights[stack[len(stack)-1]]
			stack = stack[:len(stack)-1]

			width := i
			if len(stack) > 0 {
				width = i - stack[len(stack)-1] - 1
			}

			if height*width > maxArea {
				maxArea = height * width
			}
		}
		stack = append(stack, i)
	}

	return maxArea
}

Функция numIslands подсчитывает количество островов в двумерной сетке, где '1' представляет сушу, а '0' - воду.

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

Итерация по всем ячейкам сетки
При обнаружении суши ('1') выполняется поиск в глубину (DFS)
DFS помечает все связанные участки суши как посещенные
Увеличение счетчика островов после каждого завершенного DFS

Функция numIslands:
- Проверяет входные данные на корректность
- Итерируется по всем ячейкам сетки
- Вызывает DFS для каждого найденного участка суши
- Подсчитывает количество обнаруженных островов
Функция dfs:
- Рекурсивно обходит соседние ячейки суши
- Помечает посещенные ячейки, изменяя их значение на '0'
- Проверяет границы сетки и тип ячейки (суша/вода)

Временная сложность: O(m * n), где m - количество строк, n - количество столбцов в сетке
- Каждая ячейка посещается не более одного раза
Пространственная сложность: O(m * n) в худшем случае
- Обусловлена рекурсивным стеком DFS
- Достигает максимума, если вся сетка заполнена сушей

func numIslands(grid [][]byte) int {
	if len(grid) == 0 || len(grid[0]) == 0 {
		return 0
	}

	count := 0
	for i := range grid {
		for j := range grid[i] {
			if grid[i][j] == '1' {
				dfs(grid, i, j)
				count++
			}
		}
	}
	return count
}

func dfs(grid [][]byte, i, j int) {
	if i < 0 || i >= len(grid) || j < 0 || j >= len(grid[0]) || grid[i][j] != '1' {
		return
	}

	// Помечаем текущую клетку как посещенную
	grid[i][j] = '0'

	// Рекурсивно обходим соседние клетки
	dfs(grid, i+1, j)
	dfs(grid, i-1, j)
	dfs(grid, i, j+1)
	dfs(grid, i, j-1)
}

Функция rotate выполняет поворот квадратной матрицы (изображения) на 90 градусов по часовой стрелке без использования дополнительной памяти.

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

Транспонирование матрицы (замена строк на столбцы)
Отражение каждой строки матрицы

Транспонирование матрицы:
- Обмен элементов matrix[i][j] и matrix[j][i] для i < j
- Изменяет расположение элементов по диагонали
Отражение строк:
- Обмен элементов в каждой строке: первый с последним, второй с предпоследним и т.д.
- Выполняется только для половины элементов каждой строки

Временная сложность: O(n^2), где n - размер стороны матрицы
- Транспонирование: O(n^2/2) операций
- Отражение: O(n^2/2) операций
Пространственная сложность: O(1)
- Все операции выполняются на месте, без использования дополнительной памяти

func rotate(matrix [][]int) {
	n := len(matrix)

	// Транспонируем матрицу (строки и столбцы меняем местами)
	for i := 0; i < n; i++ {
		for j := i; j < n; j++ {
			matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
		}
	}

	// Отражаем каждую строку
	for i := 0; i < n; i++ {
		for j := 0; j < n/2; j++ {
			matrix[i][j], matrix[i][n-1-j] = matrix[i][n-1-j], matrix[i][j]
		}
	}
}

Функция generateMatrix создает квадратную матрицу размером n x n, заполненную числами от 1 до n^2 в спиральном порядке по часовой стрелке.

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

Инициализация пустой матрицы размером n x n
Определение границ для заполнения (left, right, top, bottom)
Последовательное заполнение матрицы по спирали:
- Верхняя строка слева направо
- Правый столбец сверху вниз
- Нижняя строка справа налево
- Левый столбец снизу вверх
Сужение границ после каждого прохода
Повторение процесса до заполнения всей матрицы

Использование четырех указателей (left, right, top, bottom) для отслеживания границ
Применение переменной num для последовательной нумерации элементов
Использование вложенных циклов для заполнения каждой стороны спирали
Проверки условий для предотвращения повторного заполнения ячеек

Временная сложность: O(n^2)
- Каждая ячейка матрицы заполняется ровно один раз
Пространственная сложность: O(n^2)
- Для хранения результирующей матрицы

func generateMatrix(n int) [][]int {
    // Создаем матрицу n x n, заполненную нулями
    matrix := make([][]int, n)
    for i := range matrix {
        matrix[i] = make([]int, n)
    }

    // Определяем границы
    left, right := 0, n-1
    top, bottom := 0, n-1
    num := 1

    for left <= right && top <= bottom {
        // Заполняем верхнюю строку слева направо
        for col := left; col <= right; col++ {
            matrix[top][col] = num
            num++
        }
        top++

        // Заполняем правый столбец сверху вниз
        for row := top; row <= bottom; row++ {
            matrix[row][right] = num
            num++
        }
        right--

        if top <= bottom {
            // Заполняем нижнюю строку справа налево
            for col := right; col >= left; col-- {
                matrix[bottom][col] = num
                num++
            }
            bottom--
        }

        if left <= right {
            // Заполняем левый столбец снизу вверх
            for row := bottom; row >= top; row-- {
                matrix[row][left] = num
                num++
            }
            left++
        }
    }

    return matrix
}

Алгоритмы - Матрицы

Поиск максимального прямоугольника в бинарной матрице

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

Подсчет количества островов в двумерной сетке

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

Поворот изображения (матрицы) на 90 градусов по часовой стрелке

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

Генерация спиральной матрицы

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