有效的括号
leetcode：20. 有效的括号
实现
思路
遍历到左括号，入栈对应的右括号（方便遍历到右括号时进行对比）；遍历到右括号，对比栈顶元素。
把无效三种情况照顾到：1. 左括号多了（遍历结束后栈不为空）；2. 左右括号不匹配（右括号时栈顶元素与当前元素对比）；3. 右括号多了（右括号时栈是空的）。
复杂度分析
时间复杂度: O(n)
空间复杂度: O(n)
注意点
- 要先写调用.top前要避免栈是空的！（所以利用短路效应，条件先写的.empty()，防止.top空栈）
代码实现
class Solution {
public:
bool isValid(string s) {
// 左括号多了、括号不匹配、右括号多了
stack<char> st;
// 如果是奇数长度，一定无效（剪枝）
if(s.size() % 2 == 1)
return false;
for(int i = 0;i < s.size();i++){
// 左括号入栈
if(s[i] == '(') st.push(')');
else if(s[i] == '[') st.push(']');
else if(s[i] == '{') st.push('}');
// 2、3情况
else if(st.empty() || s[i] != st.top()) return false;
else{ // 否则弹出栈顶
st.pop();
}
}
// 1情况，如果结束遍历后st为空则有效，否则左括号有多余
return st.empty();
}
};
删除字符串中所有相邻重复项
leetcode：047. 删除字符串中的所有相邻重复项
用栈
思路
遍历字符串，栈顶元素与当前元素相同 ? 删除当前元素，上一元素出栈 : 当前元素入栈，继续遍历。
复杂度分析
时间复杂度：O(N)。
空间复杂度：O(N)。最坏情况字符串全部入栈。
注意点
略
代码实现
class Solution {
public:
string removeDuplicates(string s) {
// 对比栈顶元素与当前元素是否相同
// 相同则删除当前元素与上一元素
// 不相同则下一元素入栈后移遍历
stack<char> st;
for(int i = 0;i < s.size();i++){
// 栈非空且当前元素等于栈顶元素
if(!st.empty() && s[i] == st.top()){
st.pop();
}else{
st.push(s[i]);
}
}
string result = "";
while(!st.empty()){
result += st.top();
st.pop();
}
reverse(result.begin(),result.end());
return result;
}
};
逆波兰表达式求值
leetcode：150. 逆波兰表达式求值
思路
逆波兰表达式就是后缀表达式（先数字再符号）。
本质就是不停地进行两个数字的符号运算。
思路就是遇到数字入栈，遇到符号出栈两个数字做运算，结果重新入栈。
复杂度分析
时间复杂度：O(N)。
空间复杂度：O(N)。最差情况下全部入栈。
注意点
- 注意，vector
的元素是string不是char。 - 后缀表达式不需要加括号表示优先级（和中缀相比的优势）。
代码实现
class Solution {
public:
int evalRPN(vector<string>& tokens) {
// 遇到数字入栈，遇到符号出栈做运算，结果入栈
stack<long long> st;
for(string s : tokens){
if(s == "+" || s == "-" || s == "*" || s == "/"){
long long num1 = st.top(); st.pop();
long long num2 = st.top(); st.pop();
if(s == "+") st.push(num2 + num1);
else if(s == "-") st.push(num2 - num1);
else if(s == "*") st.push(num2 * num1);
else if(s == "/") st.push(num2 / num1);
}else{
st.push(stoll(s)); // string to long long
}
}
int result = st.top();
st.pop();
return result;
}
};