算法题 增减字符串匹配

942. 增减字符串匹配

问题描述

给定只含"I"（增加）和"D"（减少）的字符串s，令n = s.length。

根据s构造一个排列perm（长度为n + 1），使得对于所有的i：

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

返回满足条件的任意一个排列perm。

示例：

输入: s = "IDID" 输出: [0,4,1,3,2] 解释: - I: 0 < 4 - D: 4 > 1 - I: 1 < 3 - D: 3 > 2 输入: s = "III" 输出: [0,1,2,3] 输入: s = "DDI" 输出: [3,2,0,1] 解释: - D: 3 > 2 - D: 2 > 0 - I: 0 < 1

算法思路

贪心：

核心思想：

• 使用两个指针：low = 0和high = n
• 遍历字符串s：
  • 如果遇到'I'，选择当前最小可用数字low，然后low++
  • 如果遇到'D'，选择当前最大可用数字high，然后high--
• 最后将剩余的数字（此时low == high）添加到结果末尾

代码实现

方法一：双指针贪心

classSolution{/** * 根据增减字符串构造排列 * * @param s 只包含 'I' 和 'D' 的字符串 * @return 满足条件的排列数组 */publicint[]diStringMatch(Strings){intn=s.length();int[]result=newint[n+1];intlow=0;// 当前最小可用数字inthigh=n;// 当前最大可用数字// 遍历字符串s，构造前n个元素for(inti=0;i<n;i++){if(s.charAt(i)=='I'){// 遇到'I'，选择最小的可用数字result[i]=low++;}else{// s.charAt(i) == 'D'// 遇到'D'，选择最大的可用数字result[i]=high--;}}// 最后一个位置，此时low == highresult[n]=low;// 或者 result[n] = high;returnresult;}}

算法分析

• 时间复杂度：O(n)
  • 只需要遍历字符串一次
• 空间复杂度：O(1)
  • 只使用了常数个额外变量

算法过程

输入：s = "IDID"

1. 初始化：low = 0,high = 4,result = [?, ?, ?, ?, ?]
2. i=0,s[0]='I'→result[0] = 0,low = 1
3. i=1,s[1]='D'→result[1] = 4,high = 3
4. i=2,s[2]='I'→result[2] = 1,low = 2
5. i=3,s[3]='D'→result[3] = 3,high = 2
6. 最后：result[4] = 2
7. 结果：[0,4,1,3,2]

输入：s = "DDI"

1. 初始化：low = 0,high = 3,result = [?, ?, ?, ?]
2. i=0,'D'→result[0] = 3,high = 2
3. i=1,'D'→result[1] = 2,high = 1
4. i=2,'I'→result[2] = 0,low = 1
5. 最后：result[3] = 1
6. 结果：[3,2,0,1]

输入：s = "III"

1. result[0] = 0,low = 1
2. result[1] = 1,low = 2
3. result[2] = 2,low = 3
4. result[3] = 3
5. 结果：[0,1,2,3]

测试用例

publicstaticvoidmain(String[]args){Solutionsolution=newSolution();// 测试用例1：标准示例Strings1="IDID";int[]result1=solution.diStringMatch(s1);System.out.println("Test 1: "+Arrays.toString(result1));// [0,4,1,3,2]// 验证结果verifyResult(s1,result1);// 应该输出 Valid// 测试用例2：全增加Strings2="III";int[]result2=solution.diStringMatch(s2);System.out.println("Test 2: "+Arrays.toString(result2));// [0,1,2,3]verifyResult(s2,result2);// Valid// 测试用例3：全减少Strings3="DDD";int[]result3=solution.diStringMatch(s3);System.out.println("Test 3: "+Arrays.toString(result3));// [3,2,1,0]verifyResult(s3,result3);// Valid// 测试用例4：混合情况Strings4="DDI";int[]result4=solution.diStringMatch(s4);System.out.println("Test 4: "+Arrays.toString(result4));// [3,2,0,1]verifyResult(s4,result4);// Valid// 测试用例5：单字符Strings5="I";int[]result5=solution.diStringMatch(s5);System.out.println("Test 5: "+Arrays.toString(result5));// [0,1]verifyResult(s5,result5);// ValidStrings6="D";int[]result6=solution.diStringMatch(s6);System.out.println("Test 6: "+Arrays.toString(result6));// [1,0]verifyResult(s6,result6);// Valid// 测试用例6：长字符串Strings7="IDIDIDIDID";int[]result7=solution.diStringMatch(s7);System.out.println("Test 7: Length = "+result7.length);// 11verifyResult(s7,result7);// Valid// 测试用例7：交替模式Strings8="IDIDID";int[]result8=solution.diStringMatch(s8);verifyResult(s8,result8);// ValidSystem.out.println("Test 8: Valid = "+isValidPermutation(result8,6));}privatestaticvoidverifyResult(Strings,int[]perm){booleanvalid=true;for(inti=0;i<s.length();i++){if(s.charAt(i)=='I'&&perm[i]>=perm[i+1]){valid=false;break;}if(s.charAt(i)=='D'&&perm[i]<=perm[i+1]){valid=false;break;}}// 检查是否是0到n的排列boolean[]used=newboolean[perm.length];for(intnum:perm){if(num<0||num>=perm.length||used[num]){valid=false;break;}used[num]=true;}System.out.println("验证: "+(valid?"Valid":"Invalid"));}privatestaticbooleanisValidPermutation(int[]perm,intn){boolean[]used=newboolean[n+1];for(intnum:perm){if(num<0||num>n||used[num]){returnfalse;}used[num]=true;}returntrue;}

关键点

1. 贪心策略：

   • 选择极值（最小或最大）为后续操作保留最大灵活性

2. 数字范围：

   • 必须使用0到n的所有整数恰好一次
   • 双指针保证了这一点

3. 边界处理：

   • 字符串长度为n，结果数组长度为n+1
   • 最后一个元素自动确定（low == high）

常见问题

1. 贪心策略？
   • 选择极值不会限制后续的选择空间