20.有效的括号
#栈 2024-08-15 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {  
public:  
    bool isValid(string s) {  
        stack<char> data;  
        int len = s.size();  
  
        for(int i = 0; i < len; i++){  
            if(data.empty()){  
                data.push(s[i]);  
                continue;  
            }  
  
            if((data.top() != s[i]) && ((data.top() == '(' && s[i] == ')') || (data.top() == '[' && s[i] == ']') || (data.top() == '{' && s[i] == '}'))){ // 有希望  
                data.pop();  
            }else{  
                data.push(s[i]);  
            }  
        }  
  
        if(data.empty()) return true;  
  
        return false;  
    }  
};

逐一从字符串 s 中取字符：

  1. 如果 data 栈为空，直接加入其中
  2. 如果 data 栈不为空，即将加入的字符 s[i] 与 栈中的顶部元素比较
    1. 如果不相等【data.top() != s[i]】，表明有希望匹配
    2. 如果相等，必然不可能匹配，将其加入栈中即可

栈 适合解决对称性问题，这也是栈的一个特点