三分鐘基礎之棧訓練：有效括號匹配
往期回顧
今天來判斷括號是否有效，常見題。
不知道說啥，開整吧。
LeetCode 20：有效的括號
題意
給定一個只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判斷字符串是否有效。
示例
輸入：s = "()[]{}"
輸出：true
輸入：s = "([)]"
輸出：false
提示
有效字符串需滿足：
左括號必須用相同類型右括號閉合
左括號必須以正確順序閉合
1 <= s.length <= 10^4
s 僅由括號 () [] {} 組成
題目解析
括號匹配是使用棧解決的經(jīng)典問題，難度簡單。
還不太會的臭寶看下面鏈接，本蛋寫的：
看會了棧，這道題基本就會了大半，剩下小半就是動動小腦袋瓜，稍微思考。
這題就是維護一個棧，碰到左括號就入棧，碰到右括號，取出棧頂元素，判斷棧頂元素和右括號是否匹配。
如果不匹配，返回 false，如果匹配則重復上述步驟，直到遍歷完字符串。
需要注意的是，有兩種特殊情況也是返回 false：
遍歷完整個字符串，棧不為空，說明多了左括號。
碰到右括號，但此時棧為空，說明多了右括號。
拋除上面的情況，其余的都返回 true。
圖解
假設 s = "()[]{}"
首先初始化。
# 初始化stack = []pairs = {')': '(',']': '[','}': '{'}
根據(jù)“題目解析”中說的，碰到左括號入棧，所以第 1 步，"(" 入棧
for i in s:# 如果是左括號，壓入棧if i not in pairs:stack.append(i)
接下來碰到右括號 ")"，取出棧頂元素 "("，判斷棧頂元素是否和當前右括號配對，結果發(fā)現(xiàn)配對。
既然匹配，那就繼續(xù)進行下 1 步，接下來碰到左括號 "["，入棧。
接下來碰到右括號 "]"，取出棧頂元素 "["，判斷棧頂元素是否和當前右括號配對，結果發(fā)現(xiàn)配對。
既然又匹配，那就繼續(xù)進行下 1 步，接下來碰到左括號 "{"，入棧。
接下來碰到右括號 "}"，取出棧頂元素 "{"，判斷棧頂元素是否和當前右括號配對，結果發(fā)現(xiàn)配對。
此時字符串全部遍歷完，同時棧也為空，字符串 s 有效，返回 true。
return not stack再來假設 s = "([)]"
前兩個元素都是左括號，所以直接入棧。
啥接下來碰到右括號 ")"，取出棧頂元素 "["，棧頂元素與右括號不匹配，返回 false。
# 在遍歷過程中，碰到空?；蛘呃ㄌ柌黄ヅ?，返回 False。elif not stack or pairs[i] != stack.pop():return False
每個元素的進棧或出棧的操作都是 O(1)，最壞情況下，每個元素都會進且僅進棧 1 次，所以時間復雜度為 O(1) * n = O(n)。
同理，最壞情況下，是所有的元素都入棧，所以空間復雜度也為 O(n)。
代碼實現(xiàn)
Python 代碼實現(xiàn)
class Solution:def isValid(self, s: str) -> bool:# 字符串有奇數(shù)個元素，不匹配if len(s) % 2 == 1:return False# 初始化棧stack = []pairs = {')': '(',']': '[','}': '{'}for i in s:# 如果是左括號，壓入棧if i not in pairs:stack.append(i)# 在遍歷過程中，碰到空?；蛘呃ㄌ柌黄ヅ?，返回 False。elif not stack or pairs[i] != stack.pop():return False# 全部遍歷完，如果棧為空，返回 True，棧不為空，返回 Falsereturn not stack
Java 代碼實現(xiàn)
class Solution {public boolean isValid(String s) {Deque<Character> deque = new LinkedList<>();char ch;for (int i = 0; i < s.length(); i++) {ch = s.charAt(i);//碰到左括號，就把相應的右括號入棧if (ch == '(') {deque.push(')');}else if (ch == '{') {deque.push('}');}else if (ch == '[') {deque.push(']');} else if (deque.isEmpty() || deque.peek() != ch) {return false;}else {//如果是右括號判斷是否和棧頂元素匹配deque.pop();}}//最后判斷棧中元素是否匹配return deque.isEmpty();}}
圖解有效的括號到這里就結束啦。
棧的實戰(zhàn)第一道題，題目比較簡單，寫寫畫畫仔細思考一定沒問題噠。
最后，推薦一波帥地的知識星球，歡迎熱愛學習的萌新來玩耍(閱讀原文里還有優(yōu)惠卷哦)
一個專注于校招/在校生成長的社群，這里有項目資料，大牛分享，簡歷修改，一對一問答服務，你有什么困惑，帥地都會詳細解答你，絕對物所超值，詳情可以點擊閱讀原文了解哦(原文里有優(yōu)惠卷)