目录
题目链接
注意点
- 考虑输入为空的情况
解法
解法一:如果是'('、'{'、'['这三者就入栈,否则就判断栈是否为空和栈顶括号是否与之匹配。注意两个判断顺序不可以颠倒,不然会runtime error。时间复杂度为O(n)
class Solution {
public:
bool isValid(string s) {
stack<char> stk;
for(auto &ch:s)
{
if(ch == '('||ch == '{'||ch == '[')
{
stk.push(ch);
}
else if(ch == ')')
{
if(stk.empty()||stk.top() != '(')
{
return false;
}
else
{
stk.pop();
}
}
else if(ch == '}')
{
if(stk.empty()||stk.top() != '{')
{
return false;
}
else
{
stk.pop();
}
}
else if(ch == ']')
{
if(stk.empty()||stk.top() != '[')
{
return false;
}
else
{
stk.pop();
}
}
}
if(!stk.empty())
{
return false;
}
return true;
}
};
小结
一些栈的基本操作:
- push(): 向栈内压入一个成员;
- pop(): 从栈顶弹出一个成员;(注意要判断栈是否为空)
- empty(): 如果栈为空返回true,否则返回false;
- top(): 返回栈顶,但不删除成员;(注意要判断栈是否为空)
- size(): 返回栈内元素的大小