942.增减字符串匹配

链接：942.增减字符串匹配
难度：Easy
标签：贪心、数组、双指针、字符串
简介：给定一个字符串 s ，重构排列 perm 并返回它。如果有多个有效排列 perm，则返回其中 任何一个 。

题解 1 - cpp

• 编辑时间：2022-03-24
• 执行用时：4ms
• 内存消耗：8.7MB
• 编程语言：cpp
• 解法介绍：贪心，每次 I 选最小值，D 选最大值。

class Solution {
   public:
    vector<int> diStringMatch(string s) {
        int n = s.size(), l = 0, r = s.size();
        vector<int> ans;
        for (auto &ch : s) {
            if (ch == 'I') {
                ans.push_back(l++);
            } else {
                ans.push_back(r--);
            }
        }
        ans.push_back(l++);
        return ans;
    }
};