「Code皮皮蝦」雙棧 + 貪心思路講解、程式碼實現

✨題目

解題

雙棧

思路

因為題目有*的存在，而且*既可以為左括號，也可以為右括號或者空字串，所以需要使用兩個棧來實現

leftStack棧儲存左括號的索引，starStack棧儲存星號的索引

在遍歷過程中，如果遇到右括號

優先匹配左括號，即對leftStack進行pop

如果leftStack為空，則對starStack進行pop

如果starStack為空，說明匹配不了了，直接return false

在遍歷完成之後，可能存在leftStack 和 starStack不為空的情況，那麼此時，就需要將*當作右括號，從而對括號進行匹配。

最後，如果leftStack為空，說明匹配完成，return true，否則，return false

程式碼實現

class Solution { public boolean checkValidString（String s） { //儲存左括號索引 Deque leftStack = new LinkedList<>（）； //儲存*索引 Deque starStack = new LinkedList<>（）； int n = s。length（）； for （int i = 0； i < n； i++） { char c = s。charAt（i）； if （c == ‘（’） { leftStack。push（i）； } else if （c == ‘*’） { starStack。push（i）； } else { if （！leftStack。isEmpty（）） { leftStack。pop（）； } else if （！starStack。isEmpty（）） { starStack。pop（）； } else return false； } } while （！leftStack。isEmpty（） && ！starStack。isEmpty（）） { //把*當成右括號，但是必須右括號的索引 > 左括號才能匹配 //因為是棧結構，所以根據遍歷，棧頂元素的索引是最大的索引，如果不滿足就return false if （leftStack。pop（） > starStack。pop（）） { return false； } } return leftStack。isEmpty（）； }}複製程式碼

貪心

思路

因為題目有*的存在，而*既可以為左括號，也可以為右括號或者空字串

所以我們可以維護一個未匹配左括號的範圍，即[min,max]，遍歷完成後，直接return min == 0

怎麼維護？？？

遇到左括號，則min++ , max++

遇到右括號，則min-- , max--，如果max == 0了，說了沒有可以匹配的了，那麼直接return false

遇到*號，則min-- , max++，因為*既可以為左括號，也可以為右括號

程式碼實現

class Solution { public boolean checkValidString（String s） { int min = 0， max = 0； // 維護當前左括號的數量範圍：［min， max］ char［］ chars = s。toCharArray（）； for（char i ： chars） { if（i == ‘（’） { min++； max++； }else if（i == ‘）’） { //min > 0才—— if（min > 0） min——； if（max—— == 0） return false； }else { //min > 0才—— if（min > 0） min——； max++； } } return min == 0； }}複製程式碼

精選專欄

毛遂自薦，給大家推薦一下自己的專欄，歡迎小夥伴們收藏關注

力扣演算法題解專區

小白學Java

MybatisPlus專欄

App爬蟲專欄

PC端爬蟲專欄

大廠面試題專欄

最後

創作不易，如果這篇博文對各位有幫助，希望各位小夥伴可以==一鍵三連哦！==，感謝支援，我們下次再見~~~

作者：Code皮皮蝦

連結：https：//juejin。cn/post/7012553750661300232