我们需要在原序列中挑选出一个长度为k的子序列,要求该子序列包含1, 2, ..., k,且每个数字只出现一次。字典序最小意味着我们在每一步选择时,要尽可能选择一个较小的数字。
为了解决这个问题,我们可以使用栈(Stack)来辅助选择数字。栈结构的特点是后进先出(LIFO),可以帮助我们在遍历过程中保持字典序最小。
考古学家发现了一排刻有符号的石板,共有 n 块。每块石板上刻有一个整数符号,符号的种类编号为 1 到 k。已知这 n 块石板中,每种符号都至少出现过一次。
现在需要按石板的排列顺序从中选取若干块,构成一个新的符号序列,要求序列中 1 到 k 的每种符号都恰好出现一次,并且是所有可能序列中“最小”的那个。
序列的“大小”比较规则定义如下:对于两个长度相等的序列 X=x1,x2,…,xk 和 Y=y1,y2,…,yk,从左到右依次比较对应位置的元素。设第一个满足 xieqyi 的位置为 i,如果 xi<yi,则称序列 X 小于序列 Y;若所有位置都相等,则两个序列相等。
你需要找出满足条件且按上述规则最小的符号序列。
Scan the QR code below with WeChat to sign in
First-time scan will create your account automatically
请使用微信扫描下方二维码完成注册