【05-09】力扣每日一题

今天的每日一题没想出来，难受

题目描述

题目链接，942. 增减字符串匹配，题目截图如下：

题目分析

首先我们还是按照惯例，解释下题目。题目大概意思就是，现在给你一个字符串，长度为n，并且字符串里的字符要么是I要么是D，现在我们需要用一个数组来表示这个字符串，数组的长度为n+1，数组里数字的范围为[0,n]，现在需要用[0,n]里面的数字组成一种排列，并且满足res[i]<ress[i+1]，那么s[i] = I，如果满足res[i]>res[i+1]，那么s[i] = D，最后你需要返回这个数组，如果能够有多个数组表示这个字符串，返回其中的任意一种即可。

这道题我最开始的思路是打算用回溯来做的，也就是生成[0,n]里的全排列，并且根据全排列得到我们的字符串，当字符串与我们的目标字符串相同，结束回溯，最终返回我们遍历的某一个结果即可。但是，最后超时了。所以只能换一种思路，其实就是贪心算法，贪心算法的精髓在于求解当前问题的时候选取的是当前看来最好的办法。就像我们求解函数的极值点一样，局部极小值点不一定是全局极小值点。所以我们的思路就是，遍历字符串，如果碰到的字符是I，那么表示当前数字小于后面的数字，那么当前数字我们选择目前最小的数字，那一定是满足的。如果碰到的是字符D，那么表示当前数字大于后面的数字，那么对于当前数字来说，最好的就是目前来说最大的数字，这样一来一直到循环结束即可，这便是贪心算法。

代码实现

c++代码实现如下：

class Solution {
public:
    vector<int> diStringMatch(string s) {
        int curMin = 0,curMax = s.length();
        vector<int> res;
        for(int i = 0;i<s.length();i++){
            if(s[i]=='I'){
                res.push_back(curMin);
                curMin++;
            }else{
                res.push_back(curMax);
                curMax--;
            }
        }
        res.push_back(curMin);
        return res;
    }
};