LeetCode-堆栈问题
1. 有效的括号 1\. 有效的括号
给定一个只包括 ‘(‘，’)’，’{‘，’}’，’\[‘，’\]’ 的字符串 s ，判断字符串是否有效。
有效字符串需满足：
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
思路： 频率比较高的，遍历字符，遇到左括号入栈对应右括号，直到 遇到右括号则出栈，出栈的字符是否和当前遍历的右括号相同
bool isValid(string s) {
map<char,char> m {{')','('},{']','['},{'}','{'}};
stack<char> stk;
if (s.size() % 2 != 0)
return false;
for (auto ch : s)
{
if (m.count(ch)) //判断插入的是不是右括号
{
if (stk.empty() || stk.top() != m[ch]) //如果是空的 又插入右括号， 或者顶部的括号和插入的不匹配
return false;
stk.pop(); //如果匹配 出栈
}
else {
stk.push(ch); //入栈左括号
}
}
return stk.empty(); //如果为空返回1k
}
2 . 栈模拟队列
思路： 可以使用两个栈模拟队列，一个栈用装进入队列的元素，另一个用于出队列
class MyQueue {
public:
stack<int> stIn;
stack<int> stOut;
/** Initialize your data structure here. */
MyQueue() {
}
/** Push element x to the back of queue. */
void push(int x) {
stIn.push(x);
}
/** Removes the element from in front of queue and returns that element. */
int pop() {
// 只有当stOut为空的时候，再从stIn里导入数据（导入stIn全部数据）
if (stOut.empty()) {
// 从stIn导入数据直到stIn为空
while(!stIn.empty()) {
stOut.push(stIn.top());
stIn.pop();
}
}
int result = stOut.top();
stOut.pop();
return result;
}
/** Get the front element. */
int peek() {
int res = this->pop(); // 直接使用已有的pop函数
stOut.push(res); // 因为pop函数弹出了元素res，所以再添加回去
return res;
}
/** Returns whether the queue is empty. */
bool empty() {
return stIn.empty() && stOut.empty();
}
};
3 . 队列模拟栈
思路： 一个队列而模拟栈，入栈和入队列一样，但是出的时候是最早进来的那个数，栈则是最后进来那个，每次模拟出栈的时候都应该出去的队列中最后一个
class MyStack {
public:
queue<int> que;
/** Initialize your data structure here. */
MyStack() {
}
/** Push element x onto stack. */
void push(int x) {
que.push(x);
}
/** Removes the element on top of the stack and returns that element. */
int pop() {
int size = que.size();
size--;
// 队列pop元素，只剩下一个的时候则是栈应出的元素，而pop的元素又重新进入队列
while (size--) { // 将队列头部的元素（除了最后一个元素外） 重新添加到队列尾部
que.push(que.front());
que.pop();
}
int result = que.front(); // 此时弹出的元素顺序就是栈的顺序了
que.pop();
return result;
}
/** Get the top element. */
int top() {
return que.back();
}
/** Returns whether the stack is empty. */
bool empty() {
return que.empty();
}
};
4 . 最小栈
设计一个支持 push ， pop ， top 操作，并能在常数时间内检索到最小元素的栈。
思路：
1\. 用一个辅助栈，一保存入栈的数，另一个栈保存每个数（每个栈层对应的最小值）
class MinStack {
stack<int> x_stack;
stack<int> min_stack;
public:
MinStack() {
min_stack.push(INT_MAX);
}
void push(int x) {
x_stack.push(x);
min_stack.push(min(min_stack.top(), x));
}
void pop() {
x_stack.pop();
min_stack.pop();
}
int top() {
return x_stack.top();
}
int getMin() {
return min_stack.top();
}
};
2\. 不用辅助栈，每次入栈的值为两个，一个是入栈的值，一个是当前的内的最小值 （思想还是和辅助栈一样）
class MinStack {
public:
/** initialize your data structure here. */
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;
};
4. 滑动窗口最大值 4\. 滑动窗口最大值
给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
返回 滑动窗口中的最大值 。
输入：nums = \[1,3,-1,-3,5,3,6,7\], k = 3
输出：\[3,3,5,5,6,7\]
解释：
滑动窗口的位置 最大值
\[1 3 -1\] -3 5 3 6 7 3
1 \[3 -1 -3\] 5 3 6 7 3
1 3 \[-1 -3 5\] 3 6 7 5
1 3 -1 \[-3 5 3\] 6 7 5
1 3 -1 -3 \[5 3 6\] 7 6
1 3 -1 -3 5 \[3 6 7\] 7
每次移动窗口，找到窗口中最大的数
可以自己设计一个队列，大的数总是在最前面，每次进入入栈的时候，如果入栈的数大于队列最后的数，则该最后的数pop出来，这样一来可以保持队列单调递增
class Solution {
public:
deque<int> que;
void push(int val) {
//入队列原则 入列的数若是大于 队列最后一个数则先pop出最后的数在入列 保持单调递增
while (!que.empty() && val > que.back()) {
que.pop_back();
}
que.push_back(val);
}
void pop(int val) {
//如果队列满足了k个数，出队列的数是否等于队列最前面的数
if (!que.empty() && val == que.front()) {
que.pop_front();
}
}
int getfron() { return que.front(); }
vector<int> maxSlidingWindow(vector<int> &nums, int k) {
vector<int> res;
//把k 个数先入队列
for (int i = 0; i < k; i++) {
push(nums[i]); //用编写好的push入栈
}
res.push_back(que.front());
for (int i = k; i < nums.size(); i++) {
// nums[i - k] 看下 k个数之前入队列的数是不是现在队列最起前面的
//如果是 pop出去，因为如果是的话说明队列元素已经达到
pop(nums[i - k]);
push(nums[i]);
res.push_back(getfron());
}
return res;
}
};
5. 删除字符串中的所有相邻重复项 5\. 删除字符串中的所有相邻重复项
难度简单345收藏分享切换为英文接收动态反馈
给出由小写字母组成的字符串 S，重复项删除操作会选择两个相邻且相同的字母，并删除它们。
在 S 上反复执行重复项删除操作，直到无法继续删除。
在完成所有重复项删除操作后返回最终的字符串。答案保证唯一。
思路： 字符串逐个入栈， 先入一个，入下一个的时候和栈顶的比较，如果相同，说明这两个是相邻且相同的，此时将 栈顶pop出去,遍历完字符后就是最后的结果了，此时还要反转字符串
string removeDuplicates(string S) {
stack<char> st;
for (char s : S) {
if (st.empty() || s != st.top()) {
st.push(s);
} else {
st.pop(); // s 与 st.top()相等的情况
}
}
string result = "";
while (!st.empty()) { // 将栈中元素放到result字符串汇总
result += st.top();
st.pop();
}
reverse(result.begin(), result.end()); // 此时字符串需要反转一下
return result;
}