删除相邻的同字母大小写字符对
哪些公司问过
答案要点
- 用栈存保留下来的字符,当前字符与栈顶互为大小写则弹出
- 否则入栈,最终栈内字符按顺序拼接即为结果
- 判断条件:都为字母且相差 32,或 a!=b 且忽略大小写相等
- 删除后新相邻字符自然暴露,连锁删除一次遍历完成,时间空间 O(n)
易错点
- 只判断差值 32,没确认是字母,误删 @ 和反引号之类的字符
- 把 aa 这种同大小写字符也当成一对删除
- 每删一对就从头重新扫描,复杂度退化为 O(n²)
面试官常见追问
- 需要补充哪些边界用例?
- 能不能不用额外栈空间?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。
相关面试题
- 栈和队列的区别与应用68 场
- 四则运算表达式求值15 场
- 循环队列(环形缓冲区)的实现14 场
- 最长有效括号12 场
- 滑动窗口最大值与滑动平均滤波12 场
- 有效的括号(栈)11 场
- 实现支持 O(1) 获取最小值的栈9 场
- 单调栈:下一个更大元素与每日温度6 场
- 数据流的中位数(大根堆加小根堆)5 场
- 滑动窗口最大值的单调队列解法4 场