Во-первых, определить строку «сбалансированных» скобок как строки, так что для каждого «(» есть один уникальный, соответствующий «)» где-то после этого ' (»Длина самой длинной цепи сбалансированных скобок в заданных диапазонах
Например, следующие строки являются все "сбалансированным":.
()
()()
(())()
в то время как они не являются:
) (
()) (
Дана строка скобок (длина < = 1000000), а также список запросов диапазона, найти максимальную длину сбалансированные скобки внутри каждый из диапазонов для каждого из < = 100000 запросов (с использованием 0-индексации для диапазонов)
Ex:
()))() (())
Диапазон: [0,3] -> Серия = 2: "()"
Диапазон: [0, 4] -> Серия 2 = : "()"
Диапазон: [5, 9] -> Серия = 4: "(())"
Мои мысли следующим образом:
Во-первых, просто определить, является ли Строка «сбалансирована» может быть выполнена путем сохранения стека. Если вы столкнулись с '(', нажмите в стек и когда вы столкнулись с ')', выскочите из стека. Если в конце любое '(' остается, то строка не сбалансирована.
Однако повторение этого для всех диапазонов - это сложность O (N * M), которая слишком велика для размера входов.
Теперь, заметив запросы диапазона, приходят в голову префиксные суммы и двоичные индексированные деревья/сегментные деревья. Если вы можете прекомпилировать весь префикс суммарного диапазона в массив, то вы можете найти меньшие суммы префикса, принимая разницу, который будет иметь большую сложность.
У меня возникла идея присвоить значение +1 значению '(' и -1 для a ')' таким образом, каждый раз, когда вы сталкиваетесь с '(' you добавьте один к суммарной сумме, и когда вы столкнетесь с «), вы аза. Итак, для действительной «сбалансированной» строки, например ))()
, вы получите: -1 -2 -1 -2
.
Однако, мой вопрос заключается в том, как вы используете это, чтобы определить, сбалансирован ли он? Кроме того, поскольку вам нужно найти самую большую «сбалансированную» строку в течение заданного интервала, как вы используете возможность проверить, является ли данная подстрока «сбалансированной», чтобы найти ее самой большой за этот интервал.
Есть ли способ, который может гарантировать производительность журнала N? Или иначе какие-либо оптимизации, которые могут быть применены к дереву для получения лучшего среднего? Балансировка дерева не может работать в этом случае, потому что вам нужно сохранить иерархию, не так ли? – 1110101001
@ user2612743 Я думаю, что есть две проблемные ситуации: 1) у узла может быть много детей - рассмотрим '(()()() ...())' и 2) глубина дерева велика - рассмотрим '(((...))) '. Задача 1 может быть решена путем преобразования 'k' в двоичное дерево с узлами' 2k-1', в основном вводя некоторые «фиктивные скобки» для дополнительной группировки: '([[()()] [()()]] [()()]) '. Тем не менее, я не вижу простого способа сделать что-то о глубине дерева. –