栈
用栈实现队列
class MyQueue {
private:
stack<int> st_in; // 输入栈,用于压入传入的数据
stack<int> st_out; // 输出栈,st_out为st_in的倒序
public:
MyQueue() {}
void push(int x) {
st_in.push(x);
}
int pop() {
if (st_out.empty()) {
while (!st_in.empty()) {
st_out.push(st_in.top());
st_in.pop();
}
}
int out = st_out.top();
st_out.pop();
return out;
}
int peek() {
int out = this->pop();
st_out.push(out);
return out;
}
bool empty() { return st_in.empty() && st_out.empty(); }
};
最小栈 (Hot 100)
class MinStack {
private:
stack<int>x_stack;
stack<int>min_stack; // size与x_stack相同,存储当前最小值
public:
MinStack() {
min_stack.push(INT_MAX);
}
void push(int val) {
x_stack.push(val);
min_stack.push(min(min_stack.top(),val));
}
void pop() {
x_stack.pop();
min_stack.pop();
}
int top() {
return x_stack.top();
}
int getMin() {
return min_stack.top();
}
};
有效的括号 (Hot 100)
class Solution {
public:
bool isValid(string s) {
if (s.size() % 2 != 0) return false;
stack<char> st;
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('}');
// 不匹配或者还没遍历完,栈为空
// 注意,不能是(s[i] != st.top() ||st.empty()),因为空栈没有.top()
else if (st.empty()||st.top() != s[i]) return false;
else st.pop();
}
return st.empty(); // 栈为空,则有效
}
};
字符串解码 (Hot 100)
class Solution {
public:
string decodeString(string s) {
stack<pair<string, int>> matchStack;
string cur_str;
int multi = 0;
for (char& ch : s) {
if (ch == '[') {
matchStack.push({cur_str, multi});
multi = 0;
cur_str.clear();
} else if (ch == ']') {
auto [pre_str, cnt] = matchStack.top();
matchStack.pop(); // pre_str是上个 [ 到当前 [ 的字符串,例如 "3[a2[c]]" 中的 a;
for (int i = 0; i < cnt; i++)
pre_str += cur_str;
cur_str = pre_str;
} else if (ch >= '0' and ch <= '9') {
multi = multi * 10 + (int)(ch - '0');
} else
cur_str += ch;
}
return cur_str;
}
};
每日温度 (Hot 100)
class Solution {
public:
vector<int> dailyTemperatures(vector<int>& T) {
// 递增栈:存储温度序列中元素的索引,保证栈顶索引对应的温度从栈顶到栈底是递增的
stack<int> st;
// 结果数组,用于存储每天需要等待的天数,初始化为0
vector<int> result(T.size(), 0);
// 将第一个温度的索引压入栈中
st.push(0);
// 从第二个温度开始遍历温度序列
for (int i = 1; i < T.size(); i++) {
// 情况一:如果当前温度小于等于栈顶索引对应的温度
// 则将当前温度的索引压入栈中,因为栈中需要保持递增的温度
if (T[i] <= T[st.top()]) st.push(i);
// 情况二:如果当前温度大于s栈顶索引对应的温度
// 则弹出栈顶索引,直到找到一个比当前温度更低的温度,或者栈为空
else {
while (!st.empty() && T[i] > T[st.top()]) {
// 更新栈顶索引需要等待的天数,为当前索引减去栈顶索引
result[st.top()] = i - st.top();
st.pop();
}
st.push(i);
}
}
return result;
}
};
简化:
class Solution {
public:
vector<int> dailyTemperatures(vector<int>& T) {
stack<int> st; // 递增栈
vector<int> result(T.size(), 0);
for (int i = 0; i < T.size(); i++) {
while (!st.empty() && T[i] > T[st.top()]) {
result[st.top()] = i - st.top();
st.pop();
}
st.push(i);
}
return result;
}
};