[LeetCode]t942

由范围 [0,n] 内所有整数组成的 n + 1 个整数的排列序列可以表示为长度为 n 的字符串 s ，其中:

• 如果 perm[i] < perm[i + 1] ，那么 s[i] == 'I'
• 如果 perm[i] > perm[i + 1] ，那么 s[i] == 'D'
  给定一个字符串 s ，重构排列 perm 并返回它。如果有多个有效排列perm，则返回其中 任何一个 。

给定一个字符串 s，重构排列 perm并返回它。如果有多个有效排列perm，则返回其中 任何一个 。

示例：

输入：s = "IDID"
输出：[0,4,1,3,2]

这道题初看并明白是什么意思，但仔细观察样例发现，其实I和D指定了一种偏序关系。假设需要我们返回的数组为perm，那么有如下关系：

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

长度为 n n n的“ID”字符串s指定了一种从 0 0 0到 n n n共 n + 1 n+1 n+1个数的偏序关系。
其实观察样例就不难发现，这道题可以用贪心+双指针的方式求出一组解：

• 对于给定的长度为 n n n的字符串，给出一个从0到n、升序的数字候选“队列” Q Q Q，并设置头尾指针，分别指向它的队首和队尾。
• 遍历字符串 s s s，若当前字符为 I I I，则“取出”当前队列 Q ′ Q' Q′的最小值（通过head++操作来实现）;若当前字符为 D D D，则“取出”当前队列 Q ′ Q' Q′的最大值（通过tail---来实现）。
• 上面已经添加了 n n n个数，此时必然有 h e a d = = t a i l head==tail head==tail，再次添加 h e a d head head指向元素即可。

一个例子演示如下：

给出C++版本的代码：

#include
#include
#include
using namespace std;
class Solution {
public:
    vector diStringMatch(string s) {
        //做法：左右指针+贪心
        int n = s.size();
        vectorret;
        int head=0,tail=n;//头、尾指针
        for(int i=0;i
            if(s[i]=='I'){//当遍历到的字符是'I'时，添加“剩余”数字中的最小数字
                ret.push_back(head);
                head++;
            }
            else if(s[i]=='D'){//当遍历到的字符是'D'时，添加“剩余”数字中的最大数字
                ret.push_back(tail);
                tail--;
            }
        }
        //head=tail，直接添加元素即可
        ret.push_back(head);
        return ret;
    }
};

int main()
{
    string str="IDID";
    Solution s;
    vectorret=s.diStringMatch(str);
    for(int i=0;i
        cout< 
上述代码的例子即为上面图片讲解所示。
 
正确性证明 
一般的题解只关心代码如何实现并通过样例，这里为了严谨，运用在《算法设计与分析》课上学过的知识，证明其正确性：
 
证明：通过上述贪心算法得到的数组，一定是满足题目要求的（但不唯一）。
 利用数学归纳法，对字符串s的长度
    
     
      
       
        n
       
      
      
       n
      
     
    n进行归纳：
 
当
     
      
       
        
         n
        
        
         =
        
        
         1
        
       
       
        n=1
       
      
     n=1时：s= I ,我们显然会得到序列
     
      
       
        
         {
        
        
         0
        
        
         ,
        
        
         1
        
        
         }
        
       
       
        {0,1}
       
      
     {0,1}；当s = D时，我们显然会得到序列
     
      
       
        
         {
        
        
         1
        
        
         ,
        
        
         0
        
        
         }
        
       
       
        {1,0}
       
      
     {1,0}。易知这两种情况都是符合要求的，即
     
      
       
        
         n
        
        
         =
        
        
         1
        
       
       
        n=1
       
      
     n=1时，算法正确。
假设当
     
      
       
        
         n
        
        
         =
        
        
         2
        
        
         ,
        
        
         3
        
        
         ,
        
        
         .
        
        
         .
        
        
         .
        
        
         ,
        
        
         k
        
        
         −
        
        
         1
        
       
       
        n=2,3,...,k-1
       
      
     n=2,3,...,k−1时，上述贪心算法总能得到正确结果。
考虑当
     
      
       
        
         n
        
        
         =
        
        
         k
        
       
       
        n=k
       
      
     n=k时，最后两次挑选： 
  
当s[k-1] = I时，挑选的数字为
       
        
         
          
           N
          
         
         
          N
         
        
       N，即需要满足perm[k-1] < perm[k]。此时挑选的数为
       
        
         
          
           N
          
         
         
          N
         
        
       N，由头尾指针变化得知，最后一次挑选的数必然大于
       
        
         
          
           N
          
         
         
          N
         
        
       N；
当s[k-1] = D时，挑选的数字为
       
        
         
          
           M
          
         
         
          M
         
        
       M，即需要满足perm[k-1] < perm[k]。此时挑选的数为
       
        
         
          
           M
          
         
         
          M
         
        
       M，由头尾指针变化得知，最后一次挑选的数必然小于
       
        
         
          
           M
          
         
         
          M
         
        
       M；
 即最后两次挑选总是正确的。
 
 
同时由归纳假设得知，前面的挑选也是正确的。故当s的长度为
    
     
      
       
        k
       
      
      
       k
      
     
    k时，算法也正确。
 综上对于任意长度为
    
     
      
       
        n
       
       
        (
       
       
        n
       
       
        >
       
       
        0
       
       
        )
       
      
      
       n(n>0)
      
     
    n(n>0)的字符串s，算法总能求出符合题意的perm。正确性证毕。