增减字符串匹配（贪心+双指针）

942. 增减字符串匹配 - 力扣（LeetCode）

该题属于简单题，通过题目所给样例我们不难观察发现，如果输入' I '，则我们要保证输出的数组中相同位置的下一个数字大于该位置数字，那么我们对此进行“贪心处理”，我们为保证满足条件，我们直接选择我可选数字的最小值填入该位置

反之在输入' D '的时候，我们则选择可选数字里面的最大值填入对应位置

class Solution {
public://小就找到最小，大就找到最大
    vector diStringMatch(string s) {
        int n=s.length();
        vectornum(n+1);
        vectorans;
        for(int i=0;i<=n;i++)
        {
            num[i]=1;
        }
        for(int i=0;i=0;j--)
                {
                    if(num[j])
                    {
                        ans.push_back(j);
                        num[j]--;
                        break;
                    }
                }
            }
        }
        for(int i=0;i<=n;i++)
        {
            if(num[i])
            {
                ans.push_back(i);//注意最后还剩一个数
                break;
            }
        }
        return ans;
    }
};

这里由于我们的可选数字其实是由输入的字符串长度n决定的，相当于可选数字也是确定的

针对这点，我们可以使用双指针进行优化 

class Solution {
public:
    vector diStringMatch(string s) {
        int n=s.length();
        int r=0,l=n;
        vectorans;
        for(int i=0;i