Найдите длиннейшую валидную подстроку из () за O(n)
Реализуйте longestValidParentheses(s), возвращающую длину длиннейшей подстроки из корректно вложенных (). Требования: O(n) по времени, один проход по строке. Обработайте крайние случаи — пустая строка и строка без валидной пары дают 0; непарная ) и непарная ( обрывают текущую серию. Примеры: "(()" → 2, ")()())" → 4.
func longestValidParentheses(s string) int {
// ваш код здесь
return 0
}Допишите реализацию.
Кладём в стек индекс-сентинель -1, затем на каждой ( кладём её индекс, а на ) делаем pop. После pop, если стек не пуст, длина текущей валидной серии равна i - stack[top]; если стек опустел — кладём i как новую базу. Отслеживаем максимум — O(n) по времени, O(n) по памяти.
- ✗Хранить символы вместо индексов — без позиций длину не вычислить
- ✗Забыть сентинель
-1, благодаря которомуi - stack[top]даёт верную длину - ✗Класть индекс после опустошающего pop вместо использования его как новой базовой точки отсчёта
- →Как двунаправленный проход с двумя счётчиками решает это за O(1) памяти?
- →Почему индекс непарной
)должен стать новой базой стека?
Задача
Дана строка из ( и ). Найдите длину длиннейшей подстроки из корректно вложенных скобок. Стек хранит индексы, а не символы.
func longestValidParentheses(s string) int {
best := 0
stack := []int{-1} // сентинель: база для измерения серии
for i := 0; i < len(s); i++ {
if s[i] == '(' {
stack = append(stack, i)
} else {
stack = stack[:len(stack)-1] // pop
if len(stack) == 0 {
stack = append(stack, i) // непарная ')' — новая база
} else if run := i - stack[len(stack)-1]; run > best {
best = run
}
}
}
return best
}Сентинель -1 позволяет вычислять длину как i - stack[top]. Непарная ) опустошает стек и сама становится новой базой отсчёта. Сложность — O(n) по времени и O(n) по памяти.
