LeetCode-堆栈问题

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. 滑动窗口最大值

给你一个整数数组 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. 删除字符串中的所有相邻重复项

难度简单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;
}