用栈操作构建数组

记牢一句:数在 target 里就 Push 留下,不在就 Push 再 Pop 弹走,栈等于 target 就停。下面每帧都在套这句。

开局栈是空的,一个操作都还没有。上面这排 1 到 6 就是整数流,只能按从左到右的顺序取。目标是让栈从底到顶变成 [2,4,6]。下面这根栈每 Push 一个数就长高一层,Pop 一个就矮一层。指针从第一个数开始往右走。

指针移到整数流的 1。题目规定:只要你决定取这个数,就必须先把它 Push 进栈,没有「看一眼再决定取不取」这种选项。所以下一帧先把 1 压进去,压完再判断它该不该留。

把 1 压入栈顶,栈现在从底到顶是 [1]。再看 1 该不该留:target 是 [2,4,6],1 不在 target 里,是个多余的数,下一帧要把它 Pop 掉。

把刚压进去的 1 从栈顶 Pop 出来,栈又回到 空。对 1 这个多余的数,我们用了一对 Push 和 Pop:指针往前走了一格,但栈的内容没变。这正是「不需要的数,先压再弹」的代价。

指针移到整数流的 2。题目规定:只要你决定取这个数,就必须先把它 Push 进栈,没有「看一眼再决定取不取」这种选项。所以下一帧先把 2 压进去,压完再判断它该不该留。

把 2 压入栈顶,栈现在从底到顶是 [2]。再看 2 该不该留:target 是 [2,4,6],2 正是 target 里需要的数,留着不动,这个 Push 是有效的一步。

留下 2 之后,栈从底到顶是 [2],正好等于 target 的前 1 个 [2],对得上。但还没凑齐 target 的全部 3 个,继续取下一个数。

指针移到整数流的 3。题目规定:只要你决定取这个数,就必须先把它 Push 进栈,没有「看一眼再决定取不取」这种选项。所以下一帧先把 3 压进去,压完再判断它该不该留。

把 3 压入栈顶,栈现在从底到顶是 [2,3]。再看 3 该不该留:target 是 [2,4,6],3 不在 target 里,是个多余的数,下一帧要把它 Pop 掉。

把刚压进去的 3 从栈顶 Pop 出来,栈又回到 [2]。对 3 这个多余的数,我们用了一对 Push 和 Pop:指针往前走了一格,但栈的内容没变。这正是「不需要的数,先压再弹」的代价。

指针移到整数流的 4。题目规定:只要你决定取这个数,就必须先把它 Push 进栈,没有「看一眼再决定取不取」这种选项。所以下一帧先把 4 压进去,压完再判断它该不该留。

把 4 压入栈顶,栈现在从底到顶是 [2,4]。再看 4 该不该留:target 是 [2,4,6],4 正是 target 里需要的数,留着不动,这个 Push 是有效的一步。

留下 4 之后,栈从底到顶是 [2,4],正好等于 target 的前 2 个 [2,4],对得上。但还没凑齐 target 的全部 3 个,继续取下一个数。

指针移到整数流的 5。题目规定:只要你决定取这个数,就必须先把它 Push 进栈,没有「看一眼再决定取不取」这种选项。所以下一帧先把 5 压进去,压完再判断它该不该留。

把 5 压入栈顶,栈现在从底到顶是 [2,4,5]。再看 5 该不该留:target 是 [2,4,6],5 不在 target 里,是个多余的数,下一帧要把它 Pop 掉。

把刚压进去的 5 从栈顶 Pop 出来,栈又回到 [2,4]。对 5 这个多余的数,我们用了一对 Push 和 Pop:指针往前走了一格,但栈的内容没变。这正是「不需要的数,先压再弹」的代价。

指针移到整数流的 6。题目规定:只要你决定取这个数,就必须先把它 Push 进栈,没有「看一眼再决定取不取」这种选项。所以下一帧先把 6 压进去,压完再判断它该不该留。

把 6 压入栈顶,栈现在从底到顶是 [2,4,6]。再看 6 该不该留:target 是 [2,4,6],6 正是 target 里需要的数,留着不动,这个 Push 是有效的一步。

留下 6 之后,栈从底到顶是 [2,4,6],正好等于 target 的前 3 个 [2,4,6],对得上。而且长度已经凑齐 3 个,栈完全等于 target,可以停手了。

栈现在从底到顶是 [2,4,6],和 target 一模一样。按第三条规则,这一刻必须立即停止:不再从整数流取数,也不再做任何 Push 或 Pop。即便 n 比这更大、流里还有数,也一概不读了。

回看整个过程,操作序列是 Push、Pop、Push、Push、Pop、Push、Push、Pop、Push,一共 9 步。读到 1、3、5 这三个不在 target 里的数,各用了一对 Push、Pop;读到 2、4、6 这三个需要的数,各用了一个 Push。留下来的 2、4、6 从底到顶就是 [2,4,6],和开头说的一字不差。

边界:全连续则全是 Push;target 末值小于 n 会提前停;中间缺的数靠一对 Push、Pop 跳过。

面试重点:严格递增加升序流,使你不必真维护栈;操作数 O(n) 量级;n 只保证取得到、循环里用不上。