leetcode-----20. 有效的括号

• 链接：https://leetcode-cn.com/problems/valid-parentheses/

思路

时间复杂度：(O(n))
1、先判空，则字符串至少有一个字符；
2、若栈为空，则当前字符加入栈中，继续遍历；
3、若栈不空，则判断是否栈顶字符与当前字符匹配，不匹配则返回false 。

代码

class Solution {
public:
    bool isValid(string s) {
        int n = s.size();
        if (!n) return true;
        stack<char> stk;
        stk.push(s[0]);
        for (int i = 1; i < n; ++i) {
            if (stk.empty()) {
                stk.push(s[i]);
                continue;
            }
            if (s[i] == ')' && stk.top() == '(' || s[i] == '}' && stk.top() == '{' ||s[i] == ']' && stk.top() == '[' ) stk.pop();
            else stk.push(s[i]); 
        }
        return stk.empty();
    }
};