LeetCode 942. 增减字符串匹配

思路

双单调性

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    vector<int> diStringMatch(string s) {
        int top=s.length();
        int bottom=0;
        vector<int> res(top+1);
        for(int i=0;i<s.length();i++){
            if(s[i]=='I'){
                res[i]=bottom++;
            }else if(s[i]=='D'){
                res[i]=top--;
            }
        }
        res[s.length()]=top;
        return res;
    }
};

[^1]: