引言

栈类型的题目应该是面试中比较常见的，毕竟思路对了基本马上可以做出来。关键其实只是对于堆的思路的理解。此处在总结栈类型的题目的时候也把队列也一并介绍

栈（stack）是先入后出的
队列（queue）是先入先出的
双端队列（dueue）则是两端都可了~

更直观的请见下图

下图更加直观的展示了栈和队列的区别

下面则详细的列举了定义及函数的使用：

有效括号

Click to expand the code

最长有效括号

Click to expand the code。保持栈底元素为当前已经遍历过的元素中「最后一个没有被匹配的右括号的下标」这样才是连续成对的。空间复杂度和时间复杂度都为O（N）

移掉K位数字

需要先解读题目，数字应该是顺序不变的。那要保证尽量递增的形式.且要避免前导为0（也就是栈为空时，0不要放入）

Click to expand the code


  class Solution {
    public:
        string removeKdigits(string num, int k) {
            stack<char> stack_char;
            for(int i=0;i<num.size();i++)
            {
                //每次先检查，如果满足可以先从栈中删除一些：满足条件：从左到右为递增（小的放前面）
                while(!stack_char.empty() && k>0 && stack_char.top()>num[i])
                {
                    // 当盏不为空，且盏顶的元素大于当前的元素的时候，把栈顶的元素去掉。放入当前的元素
                    stack_char.pop();
                    k--;//计数值自减
                }
                if(stack_char.empty() && num[i]=='0')//避免了前导为0
                    continue;//跳过第一个为0
                stack_char.push(num[i]);//每次都将当前值放入
            }
    
            string result;//记录结果
            while(!stack_char.empty())
            {
                if(k>0)//如果还需要继续删除位数
                    k--;
                else //只有当不需要去除数字的时候才加入
                    result+=stack_char.top();//注意这个比下面的空间复杂度更低
                    // result=stack_char.top()+result; //每次赋值导致更高的内存消耗
                stack_char.pop();//弹出栈顶
            }
            //栈是反过来的因此需要反转一下
            reverse(result.begin(), result.end());//stl中的reverse函数，需要反转一下。因为栈是逆过来的
            return result.empty()? "0":result;//注意最后结果是否为空
    
        }
    };

string代替栈：去掉重复字母

Click to expand the code


  class Solution {
    public:
        string removeDuplicateLetters(string s) {       
           //先通过unordered_map记录每个字符出现了多少次
           unordered_map<char,int> map;
           for(auto str:s)
                map[str]++;
    
            stack<char> stack_str;//定义一个栈
            unordered_map<char,int> map_stack;//用于记录这个字符是否在栈中
            for(int i=0;i<s.size();i++)
            {
                if(map_stack[s[i]]>0)//当前已经存在于stack中了
                {
                    map[s[i]]--;
                    continue;
                }
                //否则就是不存在了~
                while(!stack_str.empty() && stack_str.top()>s[i] && map[stack_str.top()]>0)
                {//当前盏不为空，且top的元素大于s[i]，且stack_str.top()元素数量大于0，也就是后面还有
                    map_stack[stack_str.top()]=0;//记录（不在栈中）
                    stack_str.pop();//出栈
                }
                stack_str.push(s[i]);//入栈
                map_stack[s[i]]=1;//入栈记录
                map[s[i]]--;//也要记录
            }
    
           string output_str;
           while(!stack_str.empty())
           {
                output_str=stack_str.top()+output_str;//注意顺序就不需要采用reverse
                stack_str.pop();
           }
           return output_str;
        }
    };

上面方法虽然通过栈可以解决，但是却很容易出错，还需要额外记录。因此下面给出用string的解法。其实也是用了栈的思想，只是用了string可以用其函数find这样可以简化操作

Click to expand the code


  class Solution {
    public:
        string removeDuplicateLetters(string s) {
            // 注意要求是字典序最小其不能打乱字符，单纯的unordered_map解决不了~
            // 对于输入bcabc。第一个是b放入，第二个发现是c，b<c,也将c放入
            // 当遇到a，少于c,且a后面有c，所以c删掉。小于b，所以b删掉。
           
           //先通过unordered_map记录每个字符出现了多少次
           unordered_map<char,int> map;
           for(auto str:s)
           {
                map[str]++;
           }
    
           string output_str;
           for(int i=0;i<s.size();i++)
           {    
                //说明当前字符已经存在了，故此不再插入
                if(output_str.find(s[i])!=string::npos)
                {
                    map[s[i]]--;//记录这个字符的数目减一，虽然没有入栈，但是这个字符也被剔除掉了
                    continue;
                }
    
                //如果没有找到
                //且栈内不为空，且即将进栈的元素小于当前栈顶的元素，同时当前栈顶的元素也不是最后一个（map中还有）
                while(!output_str.empty() && output_str.back()>s[i] && map[output_str.back()]>0)
                {
                  //循环对比
                    output_str.pop_back();//就可以删掉（相当于出栈）
                    //注意由于原本这个字符入栈的时候已经减一了，所以这里不需要再减一
                }
                output_str.push_back(s[i]);//入栈操作
                map[s[i]]--;//入栈后减一。
           }
           return output_str;
        }
    };

简化路径

Click to expand the code。时间与空间复杂度都是O（N）

矩阵乘法计算量估算

Click to expand the code。时间复杂度和空间复杂度都为O（N）关键点是：1、每对括号包含两个矩阵。2、矩阵的乘法数量应该是matrix_1.second*matrix_2.second*matrix_1.first也就是三个不一样的数字相乘啦

参考资料

My Leetcode