题目
在书架上摆着一些书,这些书只有两种颜色,要么是黄色,要么是蓝色,突然某一天这些书被施了魔法,如果一本黄色和一本蓝色的书挨着,这两本书就会消失不见,然后右边的书会往左边移动,直到和左边的书挨着,如果这两本颜色不同,这两本书又会神秘消失。现在给你一个只包含A和B的字符串s(1<=|s|<=100000),其中A表示黄色的书,B表示蓝色的书,问这n本书中最多会消失多少本书。
输入一个字符串s,s中A表示黄色的书,B表示蓝色的书
输出最多会消失多少本书
分析
拿到这个题目后,先想到了最简单的方法
直接遍历: 即先遍历一遍将符合消除,然后遍历第二遍直到符合的全部消除,算了算法时间复杂度,为O(N^2),速度太慢,放弃
随之,想到了先排序,在进行发现复杂度更高。放弃。
遂仔细读题,发现这个问题更适合使用栈来做,算了一下时间复杂度为O(N),遂用之。
使用栈的坑:
- n<2
- 消除过程中,栈空了:在栈空了,要重新赋值给目标比较变量,同时将该字符进栈。