LeetCode1653 使字符串平衡的最少删除次数 栈解法结果异常排查

你的代码在处理逆序对（b在前a在后）时存在逻辑错误，导致示例1计数偏多，具体问题如下：

• 遇到当前字符为a且栈顶为b时，你选择弹出栈中所有的b并累加删除次数，这不是最优决策。对于每一组b+a的逆序对，我们只需要删除其中一个字符即可：要么删前面的b，要么删后面的a，仅需加1次删除次数，不需要删除前面所有的b——剩余未被删除的b只要后续没有a就不需要处理，全部删除会额外增加计数。
• 额外说明：栈声明为stack<int>存储字符是合法但不规范的，可改为stack<char>。

class Solution {
public:
    int minimumDeletions(string s) {
        int cnt = 0;
        stack<char> st;
        for (char c : s) {
            if (c == 'b') {
                st.push(c);
            } else {
                if (!st.empty() && st.top() == 'b') {
                    // 遇到逆序对，删除一个字符（删b或删a都只计数1次）
                    cnt++;
                    st.pop();
                }
            }
        }
        return cnt;
    }
};

由于我们只需要统计前面出现的b的数量，不需要实际存储所有字符，可以把栈替换为单个变量，空间复杂度从O(n)优化到O(1)，更适配1e5长度的输入：

class Solution {
public:
    int minimumDeletions(string s) {
        int cnt = 0;
        int count_b = 0;
        for (char c : s) {
            if (c == 'b') {
                count_b++;
            } else if (count_b > 0) {
                cnt++;
                count_b--;
            }
        }
        return cnt;
    }
};

内容的提问来源于stack exchange，提问作者denzil_x