day11 有效的括号 删除字符串中的所有相邻重复项 逆波兰表达式求值

题目1：20 有效的括号

题目链接：20 有效的括号

题意

判断字符串是否有效，若有效：

1）左括号必须用相应的右括号

2）左括号的闭合顺序正确? ({)}顺序不正确，应该是（{}）

3）右括号都对应相同类型的左括号

栈适合做对称匹配类的题目

分类：有3种不匹配的情况

遇到左括号，栈里放入对应的右括号；遇到右括号，就将该元素与栈口的元素进行比较

逻辑

例1：为啥要用栈，使用队列不行吗

代码

class Solution {
public:
    bool isValid(string s) {
        stack<int> st;
        //剪枝，括号匹配是2的倍数
        if(s.size()%2!=0){
            return false;
        }
        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('}');
            }
            //不匹配，右边多括号
            else if(st.empty()||s[i]!=st.top()){
                return false;
            }
            //匹配
            else{
                st.pop();
            }
        }
        //左边多括号
        return st.empty();
    }
};

• 时间复杂度: O(n)
• 空间复杂度: O(n)

题目2：1047 删除字符串中的所有相邻重复项

题目链接：1047 删除字符串中的所有相邻重复项

题意

反复删除字符串(小写字母组成)S中两个相邻的相同的字母

栈

栈非常适合解决匹配对称问题

栈中存放遍历过的元素，栈顶元素与当前遍历的元素不匹配时，就将当前元素放入栈中；如果二者匹配，就将栈顶元素弹出，但是最终返回的数组需要再reverse一下，数组中元素的顺序才正确

代码

class Solution {
public:
    string removeDuplicates(string s) {
        stack<char> st;//栈中放的是一个个字符（char类型），不是string类型
        for(int i=0;i<s.size();i++){
            if(st.empty()||st.top()!=s[i]){
                st.push(s[i]);
            }
            else{
                st.pop();
            }
        }
        string result = "";
        while(!st.empty()){
            result.push_back(st.top());//从记录到result的顺序是颠倒的
            st.pop();
        }
        reverse(result.begin(),result.end());
        return result;
    }
};

• 时间复杂度: O(n)
• 空间复杂度: O(n)

数组

受到上面栈的启发，使用数组替换也可以

直接拿着数组当作栈来使用，逻辑与栈一样，最终直接返回这个数组就可以了

代码

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

• 时间复杂度: O(n)
• 空间复杂度: O(1)，返回值不计空间复杂度

逻辑

例1：能否使用队列？

使用1个队列不合适，因为队列是先入先出的结构，会弹出不必要的元素

使用两个队列的话，第二个个队列做备份，当第一个队列对应相同的元素弹出时，再将备份队列中的元素放到第一个队列中，就是上节模拟栈的那个代码，但是会有错误，原因就是相同的元素使得最终定位查找的时候很难

题目3：150 逆波兰表达式

题目链接：150 逆波兰表达式求值

题意

计算字符串数组tokens(表示为逆波兰表达式的算术表达式）的结果

最终的结果以及中间结果可以用32位整数表示，

栈

遇到数字，则入栈，遇到运算符(+ - * /)取出栈顶的两个元素计算，将结果压入栈

逆波兰表达式就是二叉树的后序遍历(左右中)

① 注意字符串是string类型的数组，引用其中的某个元素要用""

② 注意运算顺序，nums2在前

③ 注意st定义的是int类型的，方便直接拿出来进行运算，所以最终放到st的各个string类型的数字要转化为int类型，这样才可以参与运算

代码

class Solution {
public:
    int evalRPN(vector<string>& tokens) {//tokens里面的每个元素是string类型，
        stack<int> st;//栈内元素是整数类型，栈中的元素才可以拿出来运算
        for(int i=0;i<tokens.size();i++){//这里必须使用""，因为tokens是string类型的数据
            if(tokens[i]=="+"||tokens[i]=="-"||tokens[i]=="*"||tokens[i]=="/"){
                int nums1 = st.top();
                st.pop();
                int nums2 = st.top();
                st.pop();
                if(tokens[i]=="+"){//一定要将nums2放在前面
                    st.push(nums2 + nums1);
                }
                else if(tokens[i]=="-"){
                    st.push(nums2 - nums1);
                }
                else if(tokens[i]=="*"){
                    st.push(nums2 * nums1);
                }
                else if(tokens[i]=="/"){
                    st.push(nums2 / nums1);
                }
            }
            else{
                st.push(stoi(tokens[i]));//因为st是int型的，而tokens是string类型的，所以进行类型转换
            }
        }
        int result = st.top();
        st.pop();
        return result;
    }
};

• 时间复杂度: O(n)
• 空间复杂度: O(n)