2019-12-13 刷题-2（栈）

1021 删除最外层的括号

类似括号匹配问题，可以用栈，由于只有单种括号，也可以只用计数器来做。设置一个记录左括号的计数器，遇到右括号就减一，当减为0时，找到一个原语。
代码：

时间：100%， 空间：31.37%
class Solution {
public:
    string removeOuterParentheses(string S) {
        int index = 0, left_counter = 0;
        string T = "";
        for (int i = 0; i < S.size(); i++) {
            if (S[i] == '(')
                left_counter++;
            else {
                left_counter--;
                if (left_counter == 0) {
                    T += S.substr(index + 1, i - index - 1);
                    index = i + 1;
                }
            }
        }
        return T;
    }
};

1047 删除字符串中的所有相邻重复项

比较简单的问题，用栈就可以解决，不过需要注意扫描字符串应从右向左，这样出栈顺序就与字符串方向相同了。
代码：

时间：96.5%， 空间：100%
class Solution {
public:
    string removeDuplicates(string S) {
        stack<char> s;
        for (int i = S.size() - 1; i >= 0; i--) {
            char cur = S[i];
            if (!s.empty()) {
                if (S[i] == s.top()) {
                    s.pop();
                }
                else s.push(cur);
            }
            else s.push(cur);
        }
        string r = "";
        while (!s.empty()) {
            r += s.top();
            s.pop();
        }
        return r;
    }
};