Forem: Ivan

Контейнер с наибольшим количеством воды

Ivan — Tue, 13 Sep 2022 06:28:24 +0000

Давайте разберем задачу контейнера с наибольшим количеством воды. Ее можно найти по ссылке Container With Most Water

Постановка задачи

Дан целочисленный массив значений высоты height размера n, т.е. нарисовано n вертикальных линий.

Необходимо найти две линии, которые вместе с осью X образуют контейнер, который содержит наибольшее количество воды.

Верните в качестве результата максимальное количество воды, которое может храниться в контейнере.

Примеры входных данных

Пример 1

Входные данные:
height = [1, 8, 6, 2, 5, 4, 8, 3, 7]
Результат:
49

Пример 2

Входные данные:
height = [1, 1]
Результат:
1

Решение

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

Решение по шагам

1) Сначала надо инициализировать переменную max, которую вернем в качестве результата.

var max: Int = 0

2) Затем необходимо инициализировать левый и правый указатель.

var left: Int = 0
var right: Int = height.size - 1

3) Для итерации по списку вершин реализуем цикл while. Условием окончания цикла является равенство вершин left и right, либо то что вершина right оказалась левее вершины left. На каждом этапе считаем текущий объем воды.

while (left < right) {
    val curr = Math.min(height[left], height[right]) * (right - left)
    ...
}

4) Далее сравниваем текущий объем воды с максимальным и наибольшее значение присваиваем переменной результата.

...
max = Math.max(curr, max)
...

5) Затем сравниваем левое и правое значение высоты вершин. Если правая вершина больше, то необходимо перевинуть левую вершину к центру. Иначе - двигаем правую вершину к центру.

...
if (height[left] < height[right]) {
    left++
} else {
    right--
}
...

6) В конце возвращаем переменную max в качестве результата.

...
return max

Оценка сложности

По времени - O(n). По списку выполняется один проход.
По памяти - O(1). Количество используемой памяти не зависит от размера входного массива.

Полное решение

fun maxArea(height: IntArray): Int {
    var max: Int = 0
    var left: Int = 0
    var right: Int = height.size - 1
    while (left < right) {
        val curr = Math.min(height[left], height[right]) * (right - left)
        max = Math.max(curr, max)
        if (height[left] < height[right]) {
            left++
        } else {
            right--
        }
    }
    return max
}

Обмен элементов в связном списке

Ivan — Mon, 12 Sep 2022 06:55:18 +0000

Давайте разберем задачу обмена элементов в связном списке. Ее можно найти по ссылке Swapping Nodes in a Linked List

Постановка задачи

Дана вершина связного списка head и целое число k.

Необходимо вернуть первый элемент связного списка после обмена k-го элемента от начала списка с k-м элементом с конца списка.

Примеры входных данных

Пример 1

Входные данные:
head = [1, 2, 3, 4, 5], k = 2
Результат:
[1, 4, 3, 2, 5]

Пример 2

Входные данные:
head = [7, 9, 6, 6, 7, 8, 3, 0, 9, 5], k = 5
Результат:
[7, 9, 6, 6, 8, 7, 3, 0, 9, 5]

Решение

Эта задача состоит из двух взаимосвязанных подзадач.

Первая подзадача заключается в определении k-го элемента с конца связного списка. Для решения этой задачи мы применим метод двух указателей. Вначале, быстрый указатель перемещается на k позиций вперед от начала списка. Затем оба указателя - быстрый и медленный - будут итерироваться синхронно по списку, сохраняя постоянную дистанцию в k элементов между собой. Когда быстрый указатель достигнет конца списка (указывая на null), медленный указатель будет указывать на k-й элемент с конца списка.

Вторая подзадача связана с обменом значений двух узлов в связном списке. Несмотря на свою относительную простоту, реализация этой задачи может варьироваться в зависимости от языка программирования. В случае с Kotlin, мы можем использовать функцию also для выполнения обмена значений между двумя узлами. Эта функция позволяет эффективно и безопасно обмениваться значениями между двумя объектами, минимизируя риск ошибок при переназначении значений.

Решение по шагам

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

if (head == null) return null

2) После проверки первой вершины списка, следующим шагом будет определение k-го элемента с начала списка. Для этого необходимо выполнить итерацию k раз, двигаясь по списку.

var left: ListNode? = head
var index = k - 1
while(index != 0 && left != null) {
    left = left.next
    index--
}

3) После определения k-го элемента с начала списка, следующим шагом будет нахождение k-го элемента с конца списка. Для этого воспользуемся двумя указателями: медленным (slow) и быстрым (fast).

var slow: ListNode? = head
var fast: ListNode? = head
index = k - 1
while(index != 0 && fast != null) {
    fast = fast.next
    index--
}

Затем итерируем одновременно быстрый и медленный указатели.

while(fast != null && fast.next != null) {
    fast = fast.next
    slow = slow!!.next
}

4) В заключение, чтобы обменять значения левого и правого элементов местами, воспользуемся функцией also, доступной в языке программирования Kotlin. Эта функция позволяет эффективно и безопасно обмениваться значениями между двумя объектами, минимизируя риск ошибок при переназначении значений. Используя also, можно легко менять значения узлов между собой, завершая решение задачи.

left?.`val` = slow?.`val`.also { slow?.`val` = left?.`val` }

Оценка сложности

Оценка временной сложности: O(n). Алгоритм имеет линейную временную сложность, так как мы проходимся по всем элементам списка только один раз. В процессе работы алгоритма два указателя перемещаются вдоль списка, что гарантирует линейное время выполнения.
Оценка сложности по памяти: O(1). Алгоритм обладает постоянной сложностью по памяти, поскольку использует только четыре переменные (два указателя и две дополнительные переменные для хранения текущих значений левого и правого элементов). Объем используемой памяти не зависит от размера входного списка, что делает алгоритм эффективным с точки зрения расхода памяти.

Полное решение

fun swapNodes(head: ListNode?, k: Int): ListNode? {
    if (head == null) return null

    var left: ListNode? = head
    var index = k - 1
    while(index != 0 && left != null) {
        left = left.next
        index--
    }

    var slow: ListNode? = head
    var fast: ListNode? = head
    index = k - 1
    while(index != 0 && fast != null) {
        fast = fast.next
        index--
    }

    while(fast != null && fast.next != null) {
        fast = fast.next
        slow = slow!!.next
    }

    left?.`val` = slow?.`val`.also { slow?.`val` = left?.`val` }

    return head
}

Вид сбоку бинарного дерева

Ivan — Sun, 11 Sep 2022 06:32:44 +0000

Давайте разберем задачу про вид сбоку бинарного дерева. Ее можно найти по ссылке Binary Tree Right Side View

Постановка задачи

Дан корень бинарного дерева. Представьте, что вы стоите справа от него. Верните значения всех вершин, которые вы видите, отсортированные по порядку сверху-вниз.

Примеры входных данных

Пример 1

Входные данные:
root = [1, 2, 3, null, 5, null, 4]
Результат:
[1, 3, 4]

Пример 2

Входные данные:
root = [1, null, 3]
Результат:
[1, 3]

Пример 3

Входные данные:
root = []
Результат:
[]

Решение

Задача, которую необходимо решить, связана с обходом графа в ширину. Обход графа в ширину - это алгоритм, который позволяет посетить все вершины графа, начиная с заданной вершины, просматривая сначала все вершины, находящиеся на расстоянии 1 от данной вершины, затем все вершины, находящиеся на расстоянии 2 и т.д.

Для выполнения задачи необходимо реализовать алгоритм обхода графа в ширину с дополнительной функциональностью. При обходе графа необходимо отслеживать уровень дерева, на котором мы находимся. Для этого можно использовать очередь, в которую будут добавляться все вершины, находящиеся на расстоянии k от начальной вершины. Также необходимо вести отдельный счетчик для уровня дерева.

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

Таким образом, реализация алгоритма обхода графа в ширину с отслеживанием уровня дерева позволит решить данную задачу.

Решение по шагам

1) Для начала надо проверить, не является ли входная вершина значению null

if (root == null) return emptyList()

2) Затем необходимо инициализировать результирующий список

val result: MutableList<Int> = mutableListOf()

3) Далее создаем маркерную вершину для разделения уровней

val marker: TreeNode = TreeNode(-101)

4) Потом инициилизируем двусвязный список для обхода в ширину. Добавляем в него первоначальные значения - первую вершину и разделяющуюу вершину.

val queue: ArrayDeque<TreeNode> = ArrayDeque()
queue.addLast(root)
queue.addLast(marker)

5) В цикле по очереди достаем элемент с начала очереди

while(queue.size > 1) {
    val node = queue.removeFirst()
}

6) Если этот элемент является маркером, то записываем в ответ предыдущую вершину

if (node == marker) {
    result.add(prevNode.`val`)
    queue.addLast(marker)
}

7) Если этот элемент не является маркером, то сохраняем временно предуыдущую вершину. А затем добавляем в очередь дочерние элементы.

prevNode = node
node.left?.also { queue.addLast(it) }
node.right?.also { queue.addLast(it) }

8) После выхода из цикла добавляем в ответ последний временно сохраненный результат.

result.add(prevNode.`val`)

Полное решение

fun rightSideView(root: TreeNode?): List<Int> {
    if (root == null) return emptyList()
    val result: MutableList<Int> = mutableListOf()
    val marker: TreeNode = TreeNode(-101)
    val queue: ArrayDeque<TreeNode> = ArrayDeque()
    queue.addLast(root)
    queue.addLast(marker)
    var prevNode: TreeNode = marker
    while(queue.size > 1) {
        val node = queue.removeFirst()
        if (node == marker) {
            result.add(prevNode.`val`)
            queue.addLast(marker)
        } else {
            prevNode = node
            node.left?.also { queue.addLast(it) }
            node.right?.also { queue.addLast(it) }
        }
    }
    result.add(prevNode.`val`)
    return result
}

Обход бинарного дерева

Ivan — Wed, 07 Sep 2022 04:33:19 +0000

Давайте разберем задачу обхода бинарного дерева. Ее можно найти по ссылке
Binary Tree Inorder Traversal

Постановка задачи

Дана корневая врешина бинарного дерева. Вернуть список всех вершин "по очереди".

Примеры входных данных

Пример 1

Входные данные:
root = [1, null, 2, 3]
Результат:
[1, 3, 2]

Пример 2

Входные данные:
root = []
Результат:
[]

Пример 3

Входные данные:
root = [1]
Результат:
[1]

Решение

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

Решение по шагам

1) Инициализируем результирующий список, который будет хранить вершины дерева в порядке их обхода

val res: MutableList<Int> = mutableListOf()

2) Создаем вспомогательную рекурсивную функцию helper, которая принимает текущую вершину дерева и список результатов

private fun helper(node: TreeNode?, res: MutableList<Int>) {
    if (node != null) {
        helper(node.left, res)
        res.add(node.`val`)
        helper(node.right, res)
    }
}

3) Внутри функции helper сначала проверяем текущую вершину на null. Это является базовым случаем для рекурсии и означает, что мы достигли конца дерева в данном направлении.

4) Затем рекурсивно вызываем функцию helper на левой дочерней вершине текущей вершины, что позволяет пройти все левые поддеревья.

5) После обхода левых поддеревьев, добавляем значение текущей вершины в список результатов.

6) А затем рекурсивно вызываем функцию helper на правой дочерней вершине текущей вершины, обходя таким образом все правые поддеревья.

7) В конце работы основной функции возвращаем список результатов, который теперь содержит вершины дерева в порядке симметричного обхода.

Вариации задачи

Рассмотрим так же две вариации этой задачи.

Preorder

Binary Tree Preorder Traversal

Первая вариация, когда мы добавляем значение вершины в список ответов до обхода дочерних вершин. Изменяются только шаги 4-6.

res.add(node.`val`)
helper(node.left, res)
helper(node.right, res)

4) Добавляем значение текущей вершины в список результатов.

5) Рекурсвивно вызываем функцию helper на левой дочерней вершине.

6) Рекурсвивно вызываем функцию helper на правой дочерней вершине.

Postorder

Binary Tree Postorder Traversal

Во второй вариации необходимо добавлять значение вершины в ответ после посещения дочерних вершин. Так же изменяются только шаги 4-6.

helper(node.left, res)
helper(node.right, res)
res.add(node.`val`)

4) Рекурсвивно вызываем функцию helper на левой дочерней вершине

5) Рекурсвивно вызываем функцию helper на правой дочерней вершине

6) Добавляем значение текущей вершины в список результатов

Оценка сложности алгоритма обхода бинарного дерева

Временная сложность: O(n). Алгоритм имеет линейную временную сложность, так как каждая вершина дерева посещается ровно один раз в процессе обхода. Здесь n обозначает количество вершин в дереве.
Сложность по памяти: O(n). Алгоритм обладает линейной сложностью по памяти, поскольку использует рекурсию, и глубина рекурсии может достигать n в самом худшем случае (для вырожденного дерева). Также требуется хранить результирующий список, который содержит n элементов.

Полное решение

fun inorderTraversal(root: TreeNode?): List<Int> {
    val res: MutableList<Int> = mutableListOf()
    helper(root, res)
    return res
}

private fun helper(node: TreeNode?, res: MutableList<Int>) {
    if (node != null) {
        helper(node.left, res)
        res.add(node.`val`)
        helper(node.right, res)
    }
}

Объединение интервалов

Ivan — Mon, 05 Sep 2022 04:33:55 +0000

Давайте разберем задачу объединения интервалов. Ее можно найти по ссылке Merge Intervals

Постановка задачи

Дан массив интервалов intervals, где intervals[i] = [start, end]. Необходимо объединить все перекрывающиеся интервалы и вернуть массив не перекрывающихся интервалов, который покрывает все интервалы во входных данных.

Примеры входных данных

Пример 1

Входные данные:
intervals = [[1, 3], [2, 6], [8, 10], [15, 18]]
Результат:
[[1, 6], [8, 10], [15, 18]]
Так как интервалы [1, 3] и [2, 6] пересекаются, мы объединяем их в [1, 6]

Пример 2

Входные данные:
intervals = [[1, 4], [4, 5]]
Результат:
[[1, 5]]
Интервалы [1, 4] и [4, 5] пересекаются

Решение

Нам надо идти по интервалам таким образом, чтобы находить все пересечения. Т.е. сначала необходимо взять самый левый интервал, а потом найти интервалы, пересекающиеся с ним частично или полностью. Если таковые найдутся, то возвращаем новый интервал. Если нет, то записываем исходный интервал в ответ.

Решение по шагам

1) Так как мы не знаем размер выходных данных, то для сохранения результата заведем список, потому что он масштабируется. В конце для ответа преобразуем этот список в массив.

val result: MutableList<IntArray> = mutableListOf()

2) Отсортируем входные интервалы по стартовому элементу.

val sorted = intervals.sortedBy { it[0] }

3) Заведем переменные для отслеживания левого и правого конца текущего интервала. В качестве первоначального значения переменных возьмем данные первого интервала. В дальнейшем будем итерироваться со второго элемента входных данных, с индекса 1.

var start: Int = sorted[0][0]
var end: Int = sorted[0][1]

4) Идем по всем элементам циклом. Достаем левый и правый конец очередного интервала.

var index: Int = 1
while (index < intervals.size) {
   val (eachStart, eachEnd) = sorted[index]
   ...
}

5) Если левый конец очередного интервала меньше либо равен концу текущего интервала, то интервалы пересекаются. Значит необходимо их объединить, т.е. записать в правый конец текущего интервала, в переменную end, значение конца очередного интервала - eachEnd.

if (eachStart <= end) {
    end = Math.max(eachEnd, end)
}

6) Если интервалы не пересекаются, то необходимо записать данные текущего интервала, переменные eachStart и eachEnd в список ответов. А на их место записываем данные очередного интервала.

if (eachStart <= end) {
    end = Math.max(eachEnd, end)
} else {
    result.add(intArrayOf(start, end))
    start = eachStart
    end = eachEnd
}

7) После завершения цикла необходимо добавить данные текущего интервала в ответ.

result.add(intArrayOf(start, end))

Оценка сложности

По времени - O(intervals.length). Мы проходимся по всем входным данным одним циклом.
По памяти - O(intervals.length). Мы записываем результат в список, который в общем случае линейно растет с количеством входных данных.

Полное решение

fun merge(intervals: Array<IntArray>): Array<IntArray> {
    val result: MutableList<IntArray> = mutableListOf()
    val sorted = intervals.sortedBy { it[0] }
    var start: Int = sorted[0][0]
    var end: Int = sorted[0][1]
    var index: Int = 1
    while (index < intervals.size) {
        val (eachStart, eachEnd) = sorted[index]

        if (eachStart <= end) {
            end = Math.max(eachEnd, end)
        } else {
            result.add(intArrayOf(start, end))
            start = eachStart
            end = eachEnd
        }

        index++
    }
    result.add(intArrayOf(start, end))
    return result.toTypedArray()
}

Слияние отсортированных массивов

Ivan — Wed, 31 Aug 2022 08:54:03 +0000

Давайте разберем задачу слияния двух отсортированных массивов. Ее можно найти вот здесь Merge Sorted Array

Постановка задачи

Дано два массива nums1 и nums2, отсортированных в неубывающем порядке, и два числа m и n, означающих количество элементов в соответствующих массивах.
Необходимо объединить два массива в один, отсортированный в неубывающем порядке.
Результат должен быть возвращен в массив nums1.

Пример входных данных

Пример 1

Входные даные:
nums1 = [1, 2, 3, 0, 0, 0]
m = 3
nums2 = [2, 5, 6]
n = 3
Результат:
[1, 2, 2, 3, 5, 6]

Пример 2

Входные даные:
nums1 = [1]
m = 1
nums2 = []
n = 0
Результат:
[1]

Пример 3

Входные даные:
nums1 = [0]
m = 0
nums2 = [1]
n = 1
Результат:
[1]

Решение

Нам необходимо итерироваться по каждому из массивов от начала до конца. На каждой итерации мы берем минимальный элемент и помещаем его в новый массив. Далее необходимо скопировать этот массив в nums1.
Однако в таком случаем мы будем использовать дополнительную память. Это можно оптимизировать. По условию в массиве nums1 выделено место m + n. Таким образом, если мы начнем заполнять массивы с конца, то сможем обойтись без выделения дополнительной памяти.

Решение по шагам

1) Сначала нам необходимо инициализировать счетчики.

var index1: Int = m - 1
var index2: Int = n - 1
var index: Int = m + n - 1

Для первого и второго массива мы будем использовать переменные index1 и index2, соответственно. Для отслеживания результирующего индекса будет использоваться переменная index.

2) Затем определяем условия цикла.

while (index >= 0 && index2 >= 0) {
   ...
}

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

3) Далее нам необходимо реализовать условия выбора элемента и обновления индекса

if (index1 >= 0 && nums1[index1] > nums2[index2]) {
    nums1[index] = nums1[index1]
    index1--
} else {
    nums1[index] = nums2[index2]
    index2--
}
index--

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

Оценка сложности

По времени - O(nums1.length + nums2.length). Мы полностью проходимся по каждому из массивов.
По памяти - O(1). Объем используемой памяти не зависит от размеров входных массивов, поскольку для решения задачи используются только индексы.

Полное решение

fun merge(nums1: IntArray, m: Int, nums2: IntArray, n: Int) {
    var index1: Int = m - 1
    var index2: Int = n - 1
    var index: Int = m + n - 1
    while (index >= 0 && index2 >= 0) {
        if (index1 >= 0 && nums1[index1] > nums2[index2]) {
            nums1[index] = nums1[index1]
            index1--
        } else {
            nums1[index] = nums2[index2]
            index2--
        }
        index--
    }
}

Валидация скобочной последовательности

Ivan — Mon, 22 Aug 2022 13:15:00 +0000

Давайте разберем популярную задачу валидации скобочной последовательности.
Ее можно найти вот здесь Valid Parentheses

Постановка задачи

Дана некоторая строка, содержащая символы '(', ')', '{', '}', '[' и ']'. Необходимо определить, является ли данная строка валидной скобочной последовательностью.

Скобочная последовательность является валидной при выполнении двух условий:

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

Примеры входных данных

Пример 1

() - данная строка является правильной скобочной последовательностью, так как выполняются условия 1 и 2

Пример 2

()[]{} - данная строка является правильной скобочной последовательностью, так как выполняются условия 1 и 2

Пример 3

([]) - данная строка является правильной скобочной последовательностью, так как выполняются условия 1 и 2

Пример 4

([]} - данная строка не является правильной скобочной последовательностью, так как не выполняется первое условие

Пример 5

({)} - данная строка не является правильной скобочной последовательностью, так как не выполняется второе условие

Решение

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

Для стека нам подойдет класс ArrayDeque, это реализация двухсторонней очереди.

Решение по шагам

1) Достаем очередной элемент из строки. Для этого итерируемся по строке с помощью конструкции forEach. Каждый элемент в итерации будет иметь тип Char.

s.forEach { char ->
    ...
}

2) Проверяем, является ли он открывающей или закрывающей скобкой. Для этого мы используем конструкцию when
3) Если скобка открывающая, то кладем в стек

...
when(char) {
    '(' -> stack.addLast(char)
    '[' -> stack.addLast(char)
    '{' -> stack.addLast(char)
    ...
}
...

4) Если скобка закрывающая, то достаем скобку из стека и сравниваем на соответствие
5) Если скобки соответствуют, то итерируемся дальше
6) Если скобки не соответствуют, то возвращаем false

when(char) {
    ...
    else -> if (stack.isNotEmpty() || isCorrectChar(stack.removeLast())) return false
}
...

7) В конце возвращаем true, если стек пустой, и false, если в стеке остались элементы

return stack.isEmpty()

Оптимизация

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

when(char) {
    '(' -> stack.add(')')
    '[' -> stack.add(']')
    '{' -> stack.add('}')
}

Оценка сложности

По времени - O(s.length). Мы циклом проходимся по всей строке, что дает нам O(s.length). Так же мы используем операции вставки и извлечения в конец двухсторонней очереди, что дает O(1).
По памяти - O(s.length). Максимальный размер дополнительно используемой памяти - O(s.length), так как в стэк мы не добавляем больше длины входных данных.

Полное решение

fun isValid(s: String): Boolean {
    val stack = ArrayDeque<Char>()
    s.forEach { char ->
        when(char) {
            '(' -> stack.addLast(')')
            '[' -> stack.addLast(']')
            '{' -> stack.addLast('}')
            else -> if (stack.isNotEmpty() || stack.removeLast() != char) return false
        }
    }
    return stack.isEmpty()
}