什么是棧？
棧是大家很熟悉的一種數(shù)據(jù)結(jié)構(gòu)了舔箭，人們之所以使用棧罩缴，就是為了使用其后進(jìn)先出的特性。入棧和出棧是棧的兩個(gè)靈魂操作层扶。
如圖所示箫章，以Python中的list模擬棧結(jié)構(gòu)，原始list是[1,2]镜会，通過兩次push()操作檬寂，我們先后將3,4這兩個(gè)元素加入到list中，這個(gè)操作被稱作壓棧戳表，之后我們?cè)賹?duì)list施加兩次pop()操作來模擬出棧桶至，值得注意的是，元素4雖然是最后被壓棧的元素扒袖，但卻是第一個(gè)出棧的元素塞茅，這就是我們所說棧結(jié)構(gòu)的后進(jìn)先出的特性。
leetcode #1544之整理字符串
原題如下：
給你一個(gè)由大小寫英文字母組成的字符串
s季率。
一個(gè)整理好的字符串中野瘦，兩個(gè)相鄰字符s[i]和s[i+1]，其中0<= i <= s.length-2，要滿足如下條件:
若s[i]是小寫字符鞭光，則s[i+1]不可以是相同的大寫字符吏廉。
若s[i]是大寫字符，則s[i+1]不可以是相同的小寫字符惰许。
請(qǐng)你將字符串整理好席覆，每次你都可以從字符串中選出滿足上述條件的兩個(gè)相鄰字符并刪除，直到字符串整理好為止汹买。
效果如下：
輸入：s = "leEeetcode"
輸出："leetcode"
解釋：無論你第一次選的是 i = 1 還是 i = 2佩伤，都會(huì)使 "leEeetcode" 縮減為 "leetcode" 。
思路
我們可以維護(hù)一個(gè)listr來作為處理后的字符串的緩存晦毙，并且從頭至尾遍歷原始字符串s生巡，考慮如下兩種情況：
- 如果當(dāng)前遍歷到的字符
c和r中的最后一個(gè)元素互為大小寫，那么按照題意见妒，我們將同時(shí)舍棄這個(gè)元素c孤荣，以及r中的最后一個(gè)元素。刪除r中的最后一個(gè)元素须揣，就對(duì)應(yīng)著上述的出棧動(dòng)作盐股，可以用pop()方法來實(shí)現(xiàn)。 - 如果當(dāng)前遍歷到的字符
c和r中的最后一個(gè)元素沒有大小寫關(guān)系耻卡，或者r尚為空疯汁，那么直接把當(dāng)前字符c插入到r中，作為r的最后一個(gè)元素就可以了劲赠，對(duì)應(yīng)著上述壓棧的操作涛目。
經(jīng)過上述的循環(huán)操作，就可以得到一個(gè)按題意處理過的字符串了凛澎。
其他小的知識(shí)點(diǎn)
在編寫最終程序前霹肝，考慮本例中用到的幾個(gè)小的實(shí)現(xiàn)方式。
- Python如何新建一個(gè)list塑煎？
可以用r = []和r = list()兩種方式表示 - 如何判斷兩個(gè)字符互為大小寫沫换？
兩個(gè)字符互為大小寫，意味著如果我們把兩個(gè)字符都轉(zhuǎn)成小寫（或大寫）來比較的話最铁，二者是相等的讯赏；并且把這兩個(gè)原始字符直接進(jìn)行比較的話，二者是不相等的：c1.lower() == c2.lower() and c1 != c2 - Python如何訪問list的最后一個(gè)元素冷尉？
用-1作為索引漱挎，可以訪問list中的最后一個(gè)元素：r[-1] - Python如何向list末尾插入一個(gè)元素，以及從末尾刪除一個(gè)元素雀哨？
用append(c)向list尾部插入一個(gè)元素磕谅，用pop()從list尾部刪除一個(gè)元素私爷。 - Python如何將字符數(shù)組組合成字符串？
使用join()函數(shù)膊夹，形式為str.join()衬浑。這里的str意指連接分隔符。例如'-'.join(['a','b','c'])的結(jié)果是a-b-c放刨，''.join(['a','b','c'])的結(jié)果是abc工秩。
Python實(shí)現(xiàn)的源碼
class Solution:
def makeGood(self, s: str) -> str:
# 新建一個(gè)list作為返回值的棧
r = list()
# 遍歷原始字符串
for ch in s:
# 如果當(dāng)前字符ch和r中的最后一個(gè)字符互為大小寫，那么需要?jiǎng)h除r中的最后一個(gè)元素
if r and r[-1].lower() == ch.lower() and r[-1] != ch:
r.pop()
# 否則將當(dāng)前字符ch入棧
else:
r.append(ch)
# 將r中的元素組合成字符串返回
return ''.join(r)
時(shí)間復(fù)雜度
很明顯进统，時(shí)間復(fù)雜度與原始字符串s的長(zhǎng)度相關(guān)助币，對(duì)于s中每個(gè)字符的操作時(shí)間都是常量級(jí)的，因此時(shí)間復(fù)雜度為麻昼。
如果您覺得這篇文章對(duì)您有用奠支，請(qǐng)不吝點(diǎn)贊和打賞哦馋辈。
