力扣1111.有效括号的嵌套深度

力扣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;
        }
    };
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  15
  16
  17
  18
  19
  20
  21
  22
  23

贪心

• 对于每个半括号，只要考虑它与它前一个半括号的关系即可

  • 只要相同 就不能存入同一个组(深度一定会++)
  • 不同就存入一个组

•   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];
                //不同存相同组
                else
                    res[i] = res[i-1];
            }
            return res;
        }
    };
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  15
  16