942.增减字符串匹配

题目

增减字符串匹配

思路

定义两个变量，l 表示最小值0，h表示最大值 s.size(),然后遍历当前元素，若当前元素是 I，则当前位置需要赋值 l并更新l的值，反之，则赋值h的值，并更新h的值。

题解

• 题解1

class Solution {
public:
    vector<int> diStringMatch(string s) {
        int n = s.size();
        int l = 0, h = s.size();
        vector<int> res(n + 1);
        for(int i = 0; i < s.size(); i++){
            if(s[i] == 'I')  // 当前字符是 I 时，添加此时最小的
                res[i] = l ++;
            else  // 当前字符是 D 时，添加此时最大的
                res[i] = h --;
        }
        res[n] = l; // 添加最后一个数
        return res;
    }
};

• 时间复杂度：O(n)，其中 n 是字符串 s 的长度
• 空间复杂度：O(1)，数组长度 为 n + 1，但返回值不计入空间复杂度

执行用时：4 ms, 在所有 C++ 提交中击败了88.53%的用户

内存消耗：8.4 MB, 在所有 C++ 提交中击败了73.80%的用户

通过测试用例：95 / 95