题目描述
思路解析动画文字版
一句话口诀：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 · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题