stack 总结贴 新人求米

这两天一直在刷 stack，似乎找到了一些规律

首先个人认为栈的题目分为5中

1. 纯栈模拟：比如 猫狗队列、用栈排序，逆波兰表达式求值，行星碰撞（lc 735）这些，基本就是理解题意用栈就好了
2. tree 相关，关于前中后序遍历就不说了，这里说一下 lc的两题 bst迭代器255、验证先序遍历，都是可以使用栈达到一个比较满意的复杂度
3. 计算器类的题目，这个难点就是比较繁琐，可以尝试转成逆波兰表达式
4. 栈模拟递归，比如lc中常见的 解码string、括号的分数这些，可以使用递归很好的解决，但是用栈也没问题
5. 数组题，这部分最难，需要找到规律，一般都需要使用单调栈求解，比如 接雨水、直方图中等最大矩阵，所有区间最小值和

先来个题练手把
逆波兰表达式求值，题意就是说 给你一个string，长得像这样 1 2 + 3 * = 3 3 * = 9
解：直接把所有数字存到栈里，碰到操作符弹出两个计算再压栈就好了code

1. int calculate(stack<int>& st, char op){
   
2.     int v2 = st.top(); st.pop();
   
3.     int v1 = st.top(); st.pop();
   
4.     switch (op) {
   
5.         case '+': return v1+v2;
   
6.         case '-': return v1-v2;
   
7.         case '*': return v1*v2;
   
8.         case '/': return v1/v2;
   
9.     }
   
10. }
    
11. 
    
12. int eval(vector<string> &vs) {
    
13.     stack<int> st;
    
14.     for(const auto& s: vs) {
    
15.         
    
16.         if(s.size() == 1 && !isdigit(s[0])) {
    
17.             // op
    
18.             st.push(calculate(st,s[0]));
    
19.         }
    
20.         else{
    
21.             // val
    
22.             st.push(stoi(s));
    
23.         }
    
24.     }
    
25.     return st.top();
    
26. }

复制代码

很直接，这里没有考虑除0这些问题，面试的时候别忘了先确认一下

猫狗队列：这题就是考虑加一个时间戳就好了，两个队列，每个队列里面都是 pair<Pat, int>, 其中的int 使用一个计数作为时间戳。

第二个分类
其中bst 迭代器是一个比较经典的题目，就是需要我们把先序遍历的过程缓慢化，跟简单点stack 实现一样，附上code

1. class Soultion{
   
2. public:
   
3.     void build(TreeNode* root) {
   
4.         while(root!=NULL) {
   
5.             st.push(root);
   
6.             root=root->left;
   
7.         }
   
8.     }
   
9. 
   
10.     int next(){
    
11.         if(st.empty()) return -1;
    
12.         auto tp = st.top(); st.pop();
    
13.         build(tp->right);
    
14.         return tp->val;
    
15.     }
    
16. 
    
17. private:
    
18.     stack<TreeNode*> st;
    
19. };

复制代码

验证先序遍历
使用navie的方法可以这么做，对于[i,j] 这一段，我们在里面先确定root i, 然后 i+1 扫到 k，其中 [i+1,k] 这一段都小于 v=arr, 并且判断后面 [k+1, j],都大于 arr。
如果 K 后面还有小于 v 的就错误，因为右子树都会大于他，然后递归判断 [i+1,k], [k+1,j]  。
复杂度 O(n2) 最坏


优化
思路来源

您好！
本帖隐藏的内容需要积分高于 133 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 133 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

后面三个标签晚点再更新





补充内容 (2019-9-14 13:17):
只能补充不能修改了吗

补充内容 (2019-9-14 13:20):
两道限制stack
leetcode 中，
一道是删除重复字母，
一道是，一个数组，元素0-9，返回选出n个元素能组成的最大值  比如 1 4 8 6 9 5 4 选5个，就是86954

思路就是我们先把限制拿掉，看看要在呢么做
竟然到顶了。...

新人不太懂，图片没法放到正确的位置，并且字体莫名其妙就斜体了

新开个帖子把，这太难改了

楼主写的很好啊~加个好友交流一下刷题心得吧~!

大米 ++++