線上程式設計--41.神秘消失

題目

在書架上擺着一些書，這些書隻有兩種顔色，要麼是黃色，要麼是藍色，突然某一天這些書被施了魔法，如果一本黃色和一本藍色的書挨着，這兩本書就會消失不見，然後右邊的書會往左邊移動，直到和左邊的書挨着，如果這兩本顔色不同，這兩本書又會神秘消失。現在給你一個隻包含A和B的字元串s(1<=|s|<=100000)，其中A表示黃色的書，B表示藍色的書，問這n本書中最多會消失多少本書。

輸入一個字元串s，s中A表示黃色的書，B表示藍色的書

輸出最多會消失多少本書

分析

拿到這個題目後，先想到了最簡單的方法

直接周遊： 即先周遊一遍将符合消除，然後周遊第二遍直到符合的全部消除，算了算法時間複雜度，為O(N^2)，速度太慢，放棄

随之，想到了先排序，在進行發現複雜度更高。放棄。

遂仔細讀題，發現這個問題更适合使用棧來做，算了一下時間複雜度為O（N），遂用之。

使用棧的坑：

• n<2
• 消除過程中，棧空了：在棧空了，要重新指派給目标比較變量，同時将該字元進棧。

源碼

相關源碼請參考：

https://code.aliyun.com/xinYe/aliProgrammaCode/blob/master/41-%E7%A5%9E%E7%A7%98%E6%B6%88%E5%A4%B1.txt