32. 최 장 괄호
예제 1: 입력: "()" 출력: 2 설명: 최 장 유효 괄호 문자열 은 "()" 입 니 다.
예제 2: 입력: ") ()" 출력: 4 설명: 가장 길 고 유효한 괄호 문자열 은 "() ()" 입 니 다.
사고 문 제 는 가장 긴 괄호 서열 을 구 하 는 것 으로 스 택 이라는 데이터 구 조 를 사용 하 는 것 을 쉽게 생각 할 수 있다.기본 적 인 사 고 는 하나의 스 택 을 유지 하고 왼쪽 괄호 를 만나면 스 택 에 들 어가 고 오른쪽 괄호 를 만나면 스 택 에서 나 오 며 현재 합 법 적 인 서열 이 가장 긴 서열 인지 판단 하 는 것 이다.그러나 이 문 제 는 생각 이 간단 해 보이 지만 까다 로 운 테스트 집 이 많다.구체 적 으로 말 하면 주요 문 제 는 오른쪽 괄호 를 만 났 을 때 현재 의 합 법 적 인 서열 의 길 이 를 어떻게 판단 하 느 냐 하 는 것 이다.비교적 건장 한 방식 은 다음 과 같다. (1) 현재 스 택 이 비어 있 으 면 현재 오른쪽 괄호 가 합 법 적 인 서열 이 없다 는 것 을 의미한다.(2) 그렇지 않 으 면 스 택 상단 요 소 를 팝 업 합 니 다. 팝 업 후 스 택 이 비어 있 으 면 현재 괄호 가 일치 하 는 것 을 설명 합 니 다. 우 리 는 합 법 적 으로 시작 하 는 출발점 start 를 유지 할 것 입 니 다. 합 법 적 인 서열 의 길 이 는 현재 요소 의 위치 - start + 1 입 니 다.그렇지 않 으 면 스 택 에 요소 가 있 으 면 현재 합 법 적 인 서열 의 길 이 는 현재 스 택 꼭대기 요소 의 위치 에서 현재 요소 의 거리 까지 입 니 다. 스 택 꼭대기 요소 뒤의 괄호 가 합 법 적 이 고 왼쪽 괄호 가 스 택 에서 나 왔 기 때 문 입 니 다.한 번 의 스 캔 만 필요 하기 때문에 알고리즘 의 시간 복잡 도 는 O (n) 이 고 공간 복잡 도 는 스 택 의 공간 이 며 최 악의 경우 모두 왼쪽 괄호 이기 때문에 O (n) 입 니 다.
#include
#include
#include
using namespace std;
class Solution {
public:
int longestValidParentheses(string s) {
if (s.empty()) return 0;
stack index;
int maxCount = 0, startIndex = 0;
for (int i = 0; i < s.length(); i++)
{
if (s.at(i) == '(') index.push(i);
else
{
if (index.empty()) startIndex = i + 1;
else
{
index.pop();
if (index.empty()) maxCount = max(maxCount, i - startIndex + 1);
else { maxCount = max(maxCount, i - index.top()); }
}
}
}
return maxCount;
}
};
int main(int argc, char* argv[])
{
string s = ")()())";
auto res = Solution().longestValidParentheses(s);
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
