力扣1111.有效括號的嵌套深度
棧模擬
-
對于每個括號求出深度
- 奇數深度存入A，偶數深度存入B
- 這樣最大程度降低最大深度
-
class Solution {public:vector<int> maxDepthAfterSplit(string s) {//因為棧中只會存(的數量 所有用一個變量即可int d = 0;vector<int> res;for(char c:s){if(c == '('){d ++; //d為當前半括號深度//奇數一個組偶數一個組res.emplace_back(d%2);}else{res.emplace_back(d%2);d --;}}return res;}};
貪心
-
對于每個半括號，只要考慮它與它前一個半括號的關系即可
- 只要相同 就不能存入同一個組(深度一定會++)
- 不同就存入一個組
-
class Solution {public:vector<int> maxDepthAfterSplit(string s) {vector<int> res(s.size(),0);for(int i=1;i<s.size();i++){//相同存不同組if(s[i] == s[i-1])res[i] = 1 - res[i-1];//不同存相同組elseres[i] = res[i-1];}return res;}};
)
)
