数据结构之栈和队列——LeetCode：155. 最小栈,20. 有效的括号，1249. 移除无效的括号
155. 最小栈
题目描述
155. 最小栈
设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。
实现 MinStack 类:
MinStack()初始化堆栈对象。void push(int val)将元素val推入堆栈。void pop()删除堆栈顶部的元素。int top()获取堆栈顶部的元素。int getMin()获取堆栈中的最小元素。
运行代码
class MinStack {
public:
MinStack() {}
void push(int x) {
if (st.size() == 0) {
st.push({x, x});
} else {
st.push({x, min(x, st.top().second)});
}
}
void pop() { st.pop(); }
int top() { return st.top().first; }
int getMin() { return st.top().second; }
private:
stack<pair<int, int>> st;
};
/**
* Your MinStack object will be instantiated and called as such:
* MinStack* obj = new MinStack();
* obj->push(val);
* obj->pop();
* int param_3 = obj->top();
* int param_4 = obj->getMin();
*/代码思路
MinStack()：构造函数，用于初始化堆栈对象，不执行任何操作。void push(int x)：- 首先检查栈是否为空。如果栈为空，将入栈元素
x和它本身组成一个整数对{x, x}推入栈中，因为此时栈中只有一个元素，它既是栈顶元素也是最小元素。 - 如果栈不为空，将入栈元素
x和当前栈顶元素中的最小元素（即min(x, st.top().second)）组成一个整数对推入栈中。这样，每次入栈时都确保栈中的每个元素都记录了当前栈中的最小元素值。
- 首先检查栈是否为空。如果栈为空，将入栈元素
void pop()：直接调用栈的pop函数删除栈顶部的元素。int top()：返回栈顶元素的第一个整数，即当前栈顶的元素值。int getMin()：返回栈顶元素的第二个整数，即当前栈中的最小元素值。
20. 有效的括号
题目描述
20. 有效的括号
给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
有效字符串需满足：
- 左括号必须用相同类型的右括号闭合。
- 左括号必须以正确的顺序闭合。
- 每个右括号都有一个对应的相同类型的左括号。
运行代码
class Solution {
public:
bool isValid(string s) {
int n = s.size();
if(n % 2) return false;
stack<char> st;
for (int i = 0; i < n; ++i) {
if(s[i] == '(') st.push(')');
else if(s[i] == '[') st.push(']');
else if(s[i] == '{') st.push('}');
else if(st.empty()) return false;
else{
char c = st.top();
st.pop();
if(c != s[i]) return false;
}
}
if(!st.empty()) return false;
return true;
}
};代码思路
bool isValid(string s)：int n = s.size();：获取输入字符串的长度。if(n % 2) return false;：如果字符串的长度是奇数，那么肯定无法形成合法的括号序列，直接返回false。stack<char> st;：创建一个字符栈，用于存储左括号，以便后续与右括号进行匹配。for (int i = 0; i < n; ++i)：遍历输入字符串中的每个字符。- 如果当前字符是左括号
'('、'['或'{'，则将对应的右括号')、']或'}'推入栈中。 - 如果当前字符是右括号，先检查栈是否为空。如果栈为空，说明没有对应的左括号，返回
false。如果栈不为空，取出栈顶元素c，并将其与当前字符进行比较。如果不相等，说明括号不匹配，返回false；如果相等，说明找到了对应的左括号，将栈顶元素弹出。
- 如果当前字符是左括号
if(!st.empty()) return false;：遍历完字符串后，如果栈不为空，说明有多余的左括号，返回false。return true;：如果上述所有条件都满足，说明输入字符串中的括号是合法有效的，返回true。
1249. 移除无效的括号
题目描述
1249. 移除无效的括号
给你一个由 '('、')' 和小写字母组成的字符串 s。
你需要从字符串中删除最少数目的 '(' 或者 ')' （可以删除任意位置的括号)，使得剩下的「括号字符串」有效。
请返回任意一个合法字符串。
有效「括号字符串」应当符合以下 任意一条 要求：
- 空字符串或只包含小写字母的字符串
- 可以被写作
AB（A连接B）的字符串，其中A和B都是有效「括号字符串」 - 可以被写作
(A)的字符串，其中A是一个有效的「括号字符串」
运行代码
class Solution {
public:
string minRemoveToMakeValid(string s) {
stack<int> st;
string result = "";
// 第一次遍历，标记需要删除的括号位置
for (int i = 0; i < s.length(); ++i) {
if (s[i] == '(') {
st.push(i);
} else if (s[i] == ')') {
if (!st.empty()) {
st.pop();
} else {
s[i] = '*';
}
}
}
// 处理剩余未匹配的左括号
while (!st.empty()) {
s[st.top()] = '*';
st.pop();
}
// 第二次遍历，构建有效字符串
for (char c : s) {
if (c!= '*') {
result += c;
}
}
return result;
}
};代码思路
- 首先遍历给定的字符串，使用栈来记录左括号的位置。
- 当遇到右括号时，如果栈不为空，说明有左括号可以与之匹配，弹出栈顶的左括号位置；如果栈为空，说明这个右括号没有对应的左括号，将其标记为需要删除（这里用特殊字符
'*'标记）。 - 遍历结束后，栈中剩下的就是没有匹配的左括号的位置，将这些位置的字符也标记为需要删除。
- 最后再次遍历字符串，将没有被标记为删除的字符加入结果字符串中。