LeetCode 942 增减字符串匹配

重构排列：根据 ID 字符串生成符合条件的排列数组

题目描述

给定一个由 'I'（Increase）和 'D'（Decrease）组成的字符串 s，重构一个由范围 [0, n] 内所有整数组成的排列 perm（长度为 n+1），满足：

• 若 s[i] == 'I'，则 perm[i] < perm[i+1]
• 若 s[i] == 'D'，则 perm[i] > perm[i+1]

示例：

• 输入：s = "ID"
• 输出：[0, 2, 1]（满足 0 < 2 且 2 > 1）

核心思路：双指针法（贪心策略）

为什么选择双指针？

• 贪心选择：每次根据当前字符（'I'或'D'）选择剩余数字中的最小值或最大值，确保后续选择仍有解。
• 双指针初始化：low=0（最小值指针），high=n（最大值指针）。
• 遍历逻辑：
  • 遇到 'I'：取当前最小值 low，low++（为后续递增预留空间）。
  • 遇到 'D'：取当前最大值 high，high--（为后续递减预留空间）。
• 最后处理：遍历结束后，low和high重合，填入最后一个位置。

算法步骤演示（以 s="ID" 为例）：

1. 初始化：low=0, high=2, perm=[_, _, _]
2. 遍历 s[0]='I'：取 low=0，perm[0]=0，low=1
3. 遍历 s[1]='D'：取 high=2，perm[1]=2，high=1
4. 处理最后一位：low=high=1，perm[2]=1
5. 结果：[0, 2, 1] ✅

代码实现（Java）

class Solution {
    public int[] diStringMatch(String s) {
        int n = s.length();
        int[] perm = new int[n + 1];
        int low = 0, high = n;
        
        for (int i = 0; i < n; i++) {
            if (s.charAt(i) == 'I') {
                perm[i] = low++; // 选最小值，指针右移
            } else {
                perm[i] = high--; // 选最大值，指针左移
            }
        }
        
        // 处理最后一个元素（此时low == high）
        perm[n] = low;
        return perm;
    }
}

复杂度分析

关键细节解析

1. 为什么双指针法能保证唯一解？

• 唯一性证明：每次选择极值（最小 / 最大）确保后续选择的合法性。例如：
  • 遇到 'I' 选最小值，后续仍有更大的数可选（递增）。
  • 遇到 'D' 选最大值，后续仍有更小的数可选（递减）。
• 数学归纳：假设前 k 位合法，第 k+1 位的选择必合法（归纳法可证）。

2. 边界情况处理

• 全'I'字符串：如 s="III"，结果为 [0,1,2,3]（全程取low）。
• 全'D'字符串：如 s="DDD"，结果为 [3,2,1,0]（全程取high）。
• 混合情况：如 s="DIDI"，结果为 [3,2,4,1,0]（按规则交替取极值）。

3. 为什么最后一位是low（或high）？

遍历结束后，low和high必然相等（共选了n个数，剩余 1 个），直接填入即可。

测试用例

扩展思考

1. 唯一性与多解性

题目允许返回任意合法解，双指针法生成的是字典序最小的解吗？

• 示例 s="ID"：字典序最小解为 [0,2,1]（与算法结果一致）。
• 结论：双指针法生成的是极值优先的解，保证合法性，但不一定是唯一解（如 s="DI" 有解 [2,0,1] 和 [1,0,2]）。

2. 算法优化

• 空间优化：无需额外数组，直接计算（但代码可读性下降）。
• 语言适配：同样适用于 Python、C++ 等语言（只需调整语法）。

3. 类似问题

• LeetCode 424. 替换后的最长重复字符（滑动窗口）
• LeetCode 56. 合并区间（贪心排序）

总结

核心思想

双指针 + 贪心策略：通过维护最小值和最大值指针，每次根据字符选择极值，确保每一步选择的最优性，最终线性时间内构造合法排列。

适用场景

• 涉及序列构造的极值选择问题。
• 需满足相邻元素大小关系的排列问题。

附录：正确性证明（数学归纳法）

基例：n=0（空字符串），返回[0]，合法。
假设：对长度为k的字符串，算法生成合法排列。
归纳：对长度为k+1的字符串：

1. 处理前k位时，low和high维护剩余可用数字。
2. 第k+1位（最后一位）填入剩余数字（必合法，因前k位已满足大小关系）。
   因此，算法对所有n≥0有效。

博客总结：
本文通过双指针法巧妙解决了排列重构问题，时间复杂度线性，空间常数。核心在于贪心选择极值，确保每一步的合法性。该思路可扩展到其他类似的序列构造问题，是贪心策略的经典应用。