增减字符串匹配 图解题解

这道题到底在问什么

输入

s = "IDID"

输出

[0,4,1,3,2]

输入

s = "III"

输出

[0,1,2,3]（一路递增）

输入

s = "DDI"

输出

[3,2,0,1]

最优解：一步一步想明白

1. 3一句话口诀：I 给最小、D 给最大，贪心填。下面每一帧都在套它。
2. 4开局：手里有 0 到 8 这 9 个数还没用，最小是 low=0，最大是 high=8。下面从左到右逐位决定放谁。
3. 5轮到第 0 位（紫色空位），字符是 'I'。绿色是已经填好的位置。当前还没用的数是 0 到 8 这一段。
4. 6'I' 表示后一个要比它大，所以放最小的 0 最稳，剩下的数全都比它大。放完 low 前进到 1。
5. 7轮到第 1 位（紫色空位），字符是 'I'。绿色是已经填好的位置。当前还没用的数是 1 到 8 这一段。
6. 8'I' 表示后一个要比它大，所以放最小的 1 最稳，剩下的数全都比它大。放完 low 前进到 2。
7. 9轮到第 2 位（紫色空位），字符是 'D'。绿色是已经填好的位置。当前还没用的数是 2 到 8 这一段。
8. 10'D' 表示后一个要比它小，所以放最大的 8 最稳，剩下的数全都比它小。放完 high 后退到 7。
9. 11轮到第 3 位（紫色空位），字符是 'D'。绿色是已经填好的位置。当前还没用的数是 2 到 7 这一段。
10. 12'D' 表示后一个要比它小，所以放最大的 7 最稳，剩下的数全都比它小。放完 high 后退到 6。
11. 13轮到第 4 位（紫色空位），字符是 'I'。绿色是已经填好的位置。当前还没用的数是 2 到 6 这一段。
12. 14'I' 表示后一个要比它大，所以放最小的 2 最稳，剩下的数全都比它大。放完 low 前进到 3。
13. 15轮到第 5 位（紫色空位），字符是 'D'。绿色是已经填好的位置。当前还没用的数是 3 到 6 这一段。
14. 16'D' 表示后一个要比它小，所以放最大的 6 最稳，剩下的数全都比它小。放完 high 后退到 5。
15. 17轮到第 6 位（紫色空位），字符是 'I'。绿色是已经填好的位置。当前还没用的数是 3 到 5 这一段。
16. 18'I' 表示后一个要比它大，所以放最小的 3 最稳，剩下的数全都比它大。放完 low 前进到 4。
17. 19轮到第 7 位（紫色空位），字符是 'D'。绿色是已经填好的位置。当前还没用的数是 4 到 5 这一段。
18. 20'D' 表示后一个要比它小，所以放最大的 5 最稳，剩下的数全都比它小。放完 high 后退到 4。
19. 21前 8 位填完后，区间只剩一个数 4（low 和 high 撞在一起）。把它放到最后一格，排列就完整了。
20. 22这就是构造出来的排列。整段绿色表示全部就位。下面随手验两位，确认增减关系都对得上。
21. 23第 0 位是 'I'，要求 perm[0] 比 perm[1] 小：0 确实小于 1，对。
22. 24第 2 位是 'D'，要求 perm[2] 比 perm[3] 大：8 确实大于 7，对。其余各位同理，全部满足。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

from __future__ import annotations
from typing import *
from collections import *
from functools import *
from itertools import *
from math import *
from heapq import *
from bisect import *
class Solution:
    def diStringMatch(self, s: str) -> List[int]:
        low, high = 0, len(s)
        ans = []
        for c in s:
            if c == "I":
                ans.append(low)
                low += 1
            else:
                ans.append(high)
                high -= 1
        ans.append(low)
        return ans

#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
class Solution {
public:
    vector<int> diStringMatch(string s) {
        int n = s.size();
        int low = 0, high = n;
        vector<int> ans(n + 1);
        for (int i = 0; i < n; ++i) {
            if (s[i] == 'I') {
                ans[i] = low++;
            } else {
                ans[i] = high--;
            }
        }
        ans[n] = low;
        return ans;
    }
};

import java.util.*;
class Solution {
    public int[] diStringMatch(String s) {
        int n = s.length();
        int low = 0, high = n;
        int[] ans = new int[n + 1];
        for (int i = 0; i < n; i++) {
            if (s.charAt(i) == 'I') {
                ans[i] = low++;
            } else {
                ans[i] = high--;
            }
        }
        ans[n] = low;
        return ans;
    }
}

复杂度

面试官可能追问