栈
2021-10-16 16:42:19 0 举报
登录查看完整内容
算法 栈
作者其他创作
大纲/内容
)
(
匹配
a
4
字符串 s=\"()()(())\"
2左这条鱼被3右吃掉
t.peek()查看栈顶的元素
6
5
1
边界1
-1
b
消除
以此类推
将A[2]=4的下标2和A[3]=9的下标3分别入栈，满足单调栈
注意：当鱼的游动方向相同，或者相反时，并不会相遇，此时大鱼不能吃掉小鱼
小结
2
例4：字典序最小的k个数的子序列
匹配：找到符合这些特点的数据结构和算法
3
深度思考：
字符串
数组中右边第一个比我小的元素的位置，求解用递增栈
栈
需要将A[3]=9从栈中弹出，并且记录A[3]右边比它小的下标4将A[4]=4的下标4入栈
t.pop()出栈返回栈顶的值 ；会把栈顶的值删除
算法四步分析法
右括号的行为和栈的消除相似，遇到坐括号就删除故可以用栈进行消除法的模拟
记录数组
3右这条鱼被5左吃掉
例2：大鱼吃小鱼
t.peek()
代码：
模拟：模拟题目的运行
将A[4]=4的下标4入栈时，不满足单调性
边界
......
先将A[0]=1的下标0入栈
规律：尝试总结出题目的一般规律和特点
和前面同理，A[5]=0将A[4]=4弹出栈，并记录A[4]右边比它的小的下标5
先将9入栈
当遇到左括号 '(' 时，进行压栈操作当遇到右括号 ')' 时，进行弹栈操作
将0入栈，需要将栈顶元素3弹出将0入栈，不满足单调性，因为如果0将前面的元素再弹栈，余下的元素个数就小于k=3个，所以不能再利用单调性来淡出栈中元素
t.push('b')
规律
然后将A[5]=0的下标5入栈
递减栈消除：大数消除小数栈中元素递减
模拟
边界2
例3：找出数组中右边比我小的元素
广度（这种解法具有普适性吗？可以推广吗？）
深度（这种解法还可以怎么优化呢？）
边界：考虑特殊情况
分析：括号匹配会同时把左括号和右括号消除掉但是大鱼吃小鱼，只会把小鱼消除掉
较小的数消除较大的数的时候，使用递增栈要注意控制剩下的元素的个数
简单栈的特点 —— 先进后出（LIFO）顺序
然后将A[6]=5的下标6入栈，满足单调性数组遍历完毕，没有更小的值能消除栈中的元素，故将栈中元素设置为-1
弹栈的两种情况1、弹一个元素就可以2、用while语句一直弹，直到满足某个条件为止
1、字符串为空2、字符串只有1个或者奇数个3、字符串是\"(((())))\"嵌套很多层的是否可以处理
例1：判断字符串括号是否合法
当2要入栈时，不满足单调栈，需要将9出栈。由于后面还有足够多的元素，可以把9弹栈，再将2入栈
画图总结
单调栈
栈中元素一样时，只需要记录栈中元素个数
指栈中元素必须是按照升序排列的栈或者是降序排列的栈升序排列的栈称为 递增栈降序排列的栈称为 递减栈
活下来的鱼的行为（模拟中红框部分相互吃鱼的状态）就是一个栈
t.pop()
将要入栈元素1，会先弹出栈中所有元素
1左这条鱼被3右吃掉
将A[1]=2的下标1入栈，满足单调栈
当剩下的数目 + 栈中的数量 = k时，就不能消除
记录数组就是结果数组
递增栈消除：小数消除大数栈中元素递增
t.push('a')
0 条评论
回复 删除
下一页
