题目描述
思路解析
一句话答案：LeetCode 942 增减字符串匹配：遇 I 填当前最小、遇 D 填当前最大，两个指针夹着没用过的数一路收缩、末尾再补一个，就是合法排列，时间 O(n)、空间 O(1)。
只含 I 和 D 的串，要还原成怎样的排列
给一个只含 'I' 和 'D'、长度为 n 的字符串 s，要造一个由 0 到 n 这 n+1 个不同整数组成的排列 perm：s 第 i 位是 'I' 就得 perm[i]＜perm[i+1]，是 'D' 就得 perm[i]＞perm[i+1]。合法答案可能不止一个，返回任意一个即可。题面例子 s="IDID"，一个合法输出是 [0,4,1,3,2]。
把全排列都排出来逐个验，要试多少个
一个直接的办法，是把 0 到 n 的全排列一个个列出来，逐个检查每一位的增减关系对不对。可 n+1 个数的排列有 (n+1)! 种，阶乘级往上蹿，n 才十几就是上亿个，光是列完都跑不动。O((n+1)!·n) 这条路一开始就走不通。
'I' 该先给最小、'D' 该先给最大
手里攥着一段还没用过的连续整数，最小的记 low、最大的记 high。轮到 'I'，它要求后一位更大，那就把当前最小的 low 填进去——剩下没用的数全都比 low 大，后面无论接什么都拉得起这个『更大』。轮到 'D'，它要求后一位更小，就填当前最大的 high——剩下的数全比 high 小，后面那位怎么填都够小。每填一个，用掉的正好是区间的一端，剩下的仍是一段连续整数，下一步照样有最小、最大可取，不会填到中途没数可用。
两个指针怎么走，末尾为什么要单独补一格
low 从 0 起、high 从 n 起，从左到右扫 s：遇 'I' 把 low 填进答案、low 加一；遇 'D' 把 high 填进答案、high 减一。扫完 s 的 n 个字符，答案里只有 n 个数，可位置有 n+1 个——循环只填了前 n 位。这时 low 恰好等于 high，正是区间收到最后剩下的那一个数，把它补到末位，n+1 个位置才填满。
s="IDID" 四个字符，逐位填出 [0,4,1,3,2]
初始 low=0、high=4。第 0 位 'I'：填 low=0，low 变 1，答案 [0]。第 1 位 'D'：填 high=4，high 变 3，答案 [0,4]。第 2 位 'I'：填 low=1，low 变 2，答案 [0,4,1]。第 3 位 'D'：填 high=3，high 变 2，答案 [0,4,1,3]。四个字符扫完，此时 low 和 high 都等于 2，补到末位，得 [0,4,1,3,2]。回头核一眼：0＜4、4＞1、1＜3、3＞2，四段增减和 "IDID" 一位不差。
全 I、全 D 的串会填成什么样
全是 'I' 时每步都取 low，从 0 一路递增到 n，s="III" 填出 [0,1,2,3]；全是 'D' 则每步取 high，从大到小排成倒序。两种极端都自然落进同一套规则，用不着写特判。
循环一结束就返回，会少补那最后的 low，答案就短一位，根本凑不齐 0 到 n 的排列；把 'I' 填 high、'D' 填 low 放反，增减关系全体翻转，"IDID" 头一段就对不上。时间上从左到右扫一遍是 O(n)，只用 low、high 两个指针、不算输出数组是 O(1)。
▶ 动画逐步走查（文字版）——想跟着上方动画一帧帧对照就展开
一句话口诀：I 给最小、D 给最大，贪心填。下面每一帧都在套它。
开局：手里有 0 到 8 这 9 个数还没用，最小是 low=0，最大是 high=8。下面从左到右逐位决定放谁。
轮到第 0 位（紫色空位），字符是 'I'。绿色是已经填好的位置。当前还没用的数是 0 到 8 这一段。
'I' 表示后一个要比它大，所以放最小的 0 最稳，剩下的数全都比它大。放完 low 前进到 1。
轮到第 1 位（紫色空位），字符是 'I'。绿色是已经填好的位置。当前还没用的数是 1 到 8 这一段。
'I' 表示后一个要比它大，所以放最小的 1 最稳，剩下的数全都比它大。放完 low 前进到 2。
轮到第 2 位（紫色空位），字符是 'D'。绿色是已经填好的位置。当前还没用的数是 2 到 8 这一段。
'D' 表示后一个要比它小，所以放最大的 8 最稳，剩下的数全都比它小。放完 high 后退到 7。
轮到第 3 位（紫色空位），字符是 'D'。绿色是已经填好的位置。当前还没用的数是 2 到 7 这一段。
'D' 表示后一个要比它小，所以放最大的 7 最稳，剩下的数全都比它小。放完 high 后退到 6。
轮到第 4 位（紫色空位），字符是 'I'。绿色是已经填好的位置。当前还没用的数是 2 到 6 这一段。
'I' 表示后一个要比它大，所以放最小的 2 最稳，剩下的数全都比它大。放完 low 前进到 3。
轮到第 5 位（紫色空位），字符是 'D'。绿色是已经填好的位置。当前还没用的数是 3 到 6 这一段。
'D' 表示后一个要比它小，所以放最大的 6 最稳，剩下的数全都比它小。放完 high 后退到 5。
轮到第 6 位（紫色空位），字符是 'I'。绿色是已经填好的位置。当前还没用的数是 3 到 5 这一段。
'I' 表示后一个要比它大，所以放最小的 3 最稳，剩下的数全都比它大。放完 low 前进到 4。
轮到第 7 位（紫色空位），字符是 'D'。绿色是已经填好的位置。当前还没用的数是 4 到 5 这一段。
'D' 表示后一个要比它小，所以放最大的 5 最稳，剩下的数全都比它小。放完 high 后退到 4。
前 8 位填完后，区间只剩一个数 4（low 和 high 撞在一起）。把它放到最后一格，排列就完整了。
这就是构造出来的排列。整段绿色表示全部就位。下面随手验两位，确认增减关系都对得上。
第 0 位是 'I'，要求 perm[0] 比 perm[1] 小：0 确实小于 1，对。
第 2 位是 'D'，要求 perm[2] 比 perm[3] 大：8 确实大于 7，对。其余各位同理，全部满足。
边界先想清：全 I 就是 0 到 n 顺序，全 D 就是倒序。
两个高频追问：贪心为何不卡死、答案为何不唯一。
参考代码
from __future__ import annotationsfrom 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复杂度
- 时间：O(n)，从左到右扫一遍字符串
- 空间：O(1)，只用 low、high 两个指针，不计输出数组
易错点
面试追问把动画讲成自己的话
追问为什么这套贪心一定能构造出合法解，不会中途卡死？
追问合法答案是唯一的吗？
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
交替合并字符串
LeetCode 1768 · 简单 · 沿着 双指针套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题