Junyuan's Homepage

232. 用栈实现队列

题目链接：click here
文章讲解：click here
题目描述：使用栈实现队列的下列操作：

push(x) – 将一个元素放入队列的尾部。
pop() – 从队列首部移除元素。
peek() – 返回队列首部的元素。
empty() – 返回队列是否为空。
思路：
关键在于栈的输出是与输入反序的，而涉及到反序的输出，昨天的字符串恰好有启发，double 反转，就变顺序了，这里也一样，拿另一个栈先接收输出序列，再从这个栈输出的时候就是和输入顺序一致的，也就模拟了队列的行为。

进一步的，讲解中总结这种方法为输入、输出栈模式，并且有一个细节，就是每次调用pop或者peak接口的时候，如果输出栈内仍然有元素，那么就直接输出，因为里面就是最早输入“队列”的元素。而如果输出栈是空的，则本次需要先倒腾一手，把输入栈里的东西全都倒入输出栈。这样就确保了一般情况下，输入、输出都是O(1)复杂度，只有输出栈为空的时候，需要更大的开销。并且，由于所有的元素只会进、出输入输出栈各一次，所以总体复杂度还是O(n)。

代码：

class MyQueue
{
public:
    stack<int> input_s;
    stack<int> output_s;

    MyQueue()
    {
    }

    void push(int x)
    {
        input_s.push(x);
    }

    int pop()
    {
        int res = peek();
        output_s.pop();
        return res;
    }

    int peek()
    {
        if (output_s.empty())
        {
            while (!input_s.empty())
            {
                output_s.push(input_s.top());
                input_s.pop();
            }
        }
        return output_s.top();
    }

    bool empty()
    {
        return output_s.empty() && input_s.empty();
    }
};

讲解代码中，实现了pop函数，然后peak调用pop，然后再把pop出来的元素塞回输出栈，按我的写法是可以避免的。
时空复杂度分析：
O(n) 时间复杂度
O(n) 空间复杂度

225. 用队列实现栈

题目链接：click here
文章讲解：click here
题目描述：使用队列实现栈的下列操作：

push(x) – 元素 x 入栈
pop() – 移除栈顶元素
top() – 获取栈顶元素
empty() – 返回栈是否为空
思路：
这里感觉用两个队列来模拟栈的行为还比较奇怪，因为栈无法实现反序的效果。

就用一个栈吧，只能手动操作了，结合昨天字符串左右旋的思路，如果我把队列前方的n-1个元素都旋转到最后方，此时队列最前方的元素，也就是最后输入的元素，就是最先输出的，模拟了栈的行为。

细节是，这种旋转操作，如果不把最前方的元素pop出去，后续就很难维护整体的有序性了。所以这里代码要实现pop函数，然后top调用pop，并把pop出来的那个元素重新塞回队尾，也就是“栈顶”。

感觉讲解里对top直接用队列的back其实是作弊了。

代码：

class MyStack
{
public:
    queue<int> q;

    MyStack()
    {
    }

    void push(int x)
    {
        q.push(x);
    }

    int pop()
    {
        for (int i = 1; i < q.size(); i++)
        {
            q.push(q.front());
            q.pop();
        }
        int res = q.front();
        q.pop();
        return res;
    }

    int top()
    {
        int top = pop();
        q.push(top);
        return top;
    }

    bool empty()
    {
        return q.empty();
    }
};

时空复杂度分析：
O(n) 时间复杂度
O(n) 空间复杂度

20. 有效的括号

题目链接：click here
文章讲解：click here
题目描述：给定一个只包括 ‘(‘，’)’，’{‘，’}’，’[‘，’]’ 的字符串，判断字符串是否有效。

有效字符串需满足：

左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
注意空字符串可被认为是有效字符串。
思路：
字符串里只有括号类型，要判断字符串是否满足上述条件，一个个翻译即可：
1. 左括号必须用相同类型的右括号闭合 + 左括号必须以正确的顺序闭合 = 读取到右括号时，它之前一定是对应的左括号
2. 注意空字符串可被认为是有效字符串 = 特殊情况
  这种近邻相消的题目，适合用栈来做，因为每次相消后，栈顶元素就自动变为更旧的那个元素，用于与新来的元素进行比对。用讲解的话来说就是：括号匹配是使用栈解决的经典问题。
具体的，从左往右读取字符串，左括号统统入栈，读取到右括号时，检测栈顶是否为对应的左括号，进而判断。

代码：写得非常直译思路

class Solution
{
public:
    bool isValid(string s)
    {
        if (s.size() % 2 != 0)
            return false;

        stack<char> sc;
        for (auto c : s)
        {
            if (c == '(' || c == '[' || c == '{')
            {
                sc.push(c);
            }
            else
            {
                if (c == ')')
                {
                    if (!sc.empty() && sc.top() == '(')
                    {
                        sc.pop();
                    }
                    else
                    {
                        return false;
                    }
                }

                if (c == ']')
                {
                    if (!sc.empty() && sc.top() == '[')
                    {
                        sc.pop();
                    }
                    else
                    {
                        return false;
                    }
                }

                if (c == '}')
                {
                    if (!sc.empty() && sc.top() == '{')
                    {
                        sc.pop();
                    }
                    else
                    {
                        return false;
                    }
                }
            }
        }

        return sc.empty();
    }
};

时空复杂度分析：
O(n) 时间复杂度
O(n) 空间复杂度

讲解代码用到了技巧：在匹配左括号的时候，右括号先入栈，就只需要比较当前元素和栈顶相不相等就可以了

class Solution {
public:
    bool isValid(string s) {
        if (s.size() % 2 != 0) return false; // 如果s的长度为奇数，一定不符合要求
        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(']');
            // 第三种情况：遍历字符串匹配的过程中，栈已经为空了，没有匹配的字符了，说明右括号没有找到对应的左括号 return false
            // 第二种情况：遍历字符串匹配的过程中，发现栈里没有我们要匹配的字符。所以return false
            else if (st.empty() || st.top() != s[i]) return false;
            else st.pop(); // st.top() 与 s[i]相等，栈弹出元素
        }
        // 第一种情况：此时我们已经遍历完了字符串，但是栈不为空，说明有相应的左括号没有右括号来匹配，所以return false，否则就return true
        return st.empty();
    }
};

1047. 删除字符串中的所有相邻重复项

题目链接：click here
文章讲解：click here
题目描述：给出由小写字母组成的字符串 S，重复项删除操作会选择两个相邻且相同的字母，并删除它们。

在 S 上反复执行重复项删除操作，直到无法继续删除。

在完成所有重复项删除操作后返回最终的字符串。答案保证唯一。
思路：
又是相邻匹配然后相消的，只不过上一题是左右括号要匹配，这道题直接是元素相等匹配。
消除后，要将剩余的元素重新由栈转string，需要注意反序的特性。

代码：

class Solution
{
public:
    string removeDuplicates(string s)
    {
        stack<char> sc;
        for (auto c : s)
        {
            if (!sc.empty() && sc.top() == c)
            {
                sc.pop();
            }
            else
            {
                sc.push(c);
            }
        }
        string().swap(s);
        int size = sc.size();
        s.resize(size);
        for (int i = size - 1; i >= 0; i--)
        {
            s[i] = sc.top();
            sc.pop();
        }
        return s;
    }
};

时空复杂度分析：
O(n) 时间复杂度
O(n) 空间复杂度

讲解代码：进一步优化，直接以string模拟栈，进而避免由栈转字符串。

class Solution {
public:
    string removeDuplicates(string S) {
        string result;
        for(char s : S) {
            if(result.empty() || result.back() != s) {
                result.push_back(s);
            }
            else {
                result.pop_back();
            }
        }
        return result;
    }
};

时空复杂度分析：
O(n) 时间复杂度
O(1) 空间复杂度

今日收获

个人博客更新。若Blog有误或是有其他想交流的，左侧有联系方式。
复习：
今日核心思想：近邻匹配问题都是栈的强项

用栈实现队列：模拟题，double反转后顺序不变的想法再次利用，输入输出栈模拟队列。
用队列实现栈：模拟题，旋转换位思想，注意top后，为了维护顺序不变，需要将pop出来的元素重塞回队尾。
有效的括号：近邻匹配，实现技巧上，通过将压入栈的内容取反，使得后续匹配到相反内容时，实际上是检测是否相等，这个想法后续可能会推广到更一般的function上。
删除字符串中的所有相邻重复项：近邻匹配，实现技巧上，直接用vector模拟栈，避免后续栈转vector的冗余操作。
耗时：2h

Junyuan Lu(陆俊元)

代码随想录算法训练营第十天 | 232. 用栈实现队列、225. 用队列实现栈、20. 有效的括号、1047. 删除字符串中的所有相邻重复项

232. 用栈实现队列

225. 用队列实现栈

20. 有效的括号

1047. 删除字符串中的所有相邻重复项

今日收获