1. 题⽬链接：942. 增减字符串匹配

2. 题⽬描述：

3. 解法（贪⼼）：

贪⼼策略：

a. 当遇到 'I' 的时候，为了让下⼀个上升的数可选择的「范围更多」，当前选择「最⼩」的那

个数；

b. 当遇到 'D' 的时候，为了让下⼀个下降的数可选择的「范围更多」，选择当前「最⼤」的那个数。

C++ 算法代码：

class Solution 
{
public:
    vector<int> diStringMatch(string s) 
    {
        //初始化
        int n=s.size();
        int l=0,r=n;
        vector<int>t(n+1);
        //填表
        for(int i=0;i<n;i++)
        {
            if(s[i]=='I')
            {
                t[i]=l++;
            }
            else
            {
                t[i]=r--;
            }
        }
        t[n]=r;
        //返回值
        return t;
    }
};

Java 算法代码：

class Solution
{
	public int[] diStringMatch(String s)
	{
		int n = s.length();
		int left = 0, right = n; // ⽤ left，right 标记最⼩值和最⼤值
		int[] ret = new int[n + 1];
		for (int i = 0; i < n; i++)
		{
			if (s.charAt(i) == 'I')
			{
				ret[i] = left++;
			}
			else
			{
				ret[i] = right--;
			}
		}
		ret[n] = left; // 把最后⼀个数放进去
		return ret;
	}
}