【三角獸】2017散招實(shí)習(xí)面試題

題目地址：

最長(zhǎng)括號(hào)匹配

在有左右括號(hào)的字符串中找出最大長(zhǎng)度的子串，使得子串的括號(hào)能夠匹配。

https://leetcode-cn.com/problems/longest-valid-parentheses/

?

解題思路：

利用一個(gè)輔助棧進(jìn)行匹配。

如果是"("，則入棧，表示待匹配。

如果是")"。先出棧，出棧"("則表示當(dāng)前匹配成功，出棧")"則表示把上次的")"索引更新。

棧為空，則需要更新索引，更新不匹配的位置。

最后用i-sta.top()則表示當(dāng)前索引減去上次不匹配的位置。遍歷一次取最大值即可。

?

AC代碼：

class Solution { public:int longestValidParentheses(string s) {stack<int> sta;sta.push(-1); int res = 0, len = s.length();for (int i = 0; i < len; i++) {if (s[i] == '(') { // 左括號(hào)進(jìn)棧sta.push(i);} else {sta.pop();if (sta.empty()) { sta.push(i);}res = max(res, i - sta.top());}}return res;} };

?

總結(jié)

以上是生活随笔為你收集整理的三角兽散招实习面试题的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。