采用贪心反转括号控制深度时，如何确保最终字符串合法？

问题背景 #

给定整数H和仅包含(、)的合法括号字符串s（每个开括号均有对应的闭括号，且括号配对嵌套正确），需返回反转最少括号的数量，使得得到的合法括号串的最大嵌套深度不超过H。此处的字符串深度指括号的最大嵌套层数，例如字符串(()(()))的深度为3。

贪心策略与实现 #

采用贪心思路：遍历字符串时维护当前深度变量，当当前深度即将超过H时，反转当前开括号；当当前深度即将小于0时，反转当前闭括号。实现代码如下：

#include <iostream>
#include <vector>

using namespace std;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int n, H;
    cin >> n >> H;

    string s;
    cin >> s;

    int depth = 0;
    int ans = 0;
    for (int i = 0; i < s.size(); ++i) {
        if (s[i] == '(' && depth == H) {
            s[i] = ')';
            ++ans;
        }
        else if (s[i] == ')' && depth == 0) {
            s[i] = '(';
            ++ans;
        }

        if (s[i] == '(')
            ++depth;
        else
            --depth;
    }

    cout << ans;
}

核心疑问 #

虽然代码运行正常，但无法确定经过上述反转操作后，最终得到的字符串为何一定是合法的（括号正确嵌套、配对）。困惑点在于：当将开括号反转为闭括号时，该闭括号可能在后续没有对应的开括号；虽然有时会因深度即将小于0而反转闭括号，但不确定是否所有情况都能保证最终字符串合法。

合法性证明 #

要确认操作后的字符串合法，只需验证括号串合法的两个核心条件：全程遍历过程中深度始终非负，且最终深度为0。

1. 全程深度非负 #

• 初始深度为0，非负。
• 对每个字符的处理逻辑保证深度不会变负：
  • 若原字符是(：
    • 当depth < H：不反转，深度加1后仍≤H，非负。
    • 当depth == H：反转成)，深度减1后变为H-1，而题目中H是合理取值（否则原合法串的深度会超出限制，代码也不会正常运行），因此H-1 ≥ 0。
  • 若原字符是)：
    • 当depth > 0：不反转，深度减1后仍≥0。
    • 当depth == 0：反转成(，深度加1后变为1，非负。

因此，遍历全程深度始终保持非负，不会出现无匹配开括号的闭括号。

2. 最终深度为0 #

原字符串是合法的，因此(和)的数量完全相等。每次反转操作只是交换单个括号的类型，不会改变两种括号的总数差——操作后(和)的数量仍相等。

结合“全程深度非负”和“最终深度为0”这两个条件，根据括号串合法的充要规则，可直接判定操作后的字符串是合法的。

针对困惑点的解释 #

你担心的“反转的)后续无对应(”不会发生：因为全程深度非负意味着每个)出现时，前面一定有未被匹配的(；而最终深度为0则保证所有括号都能完成配对，不存在孤立的括号。

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