用栈操作构建数组 图解题解
这道题到底在问什么
- 输入
- target=[1,3], n=3
- 输出
- ["Push","Push","Pop","Push"]
- 输入
- target=[1,2,3], n=3
- 输出
- ["Push","Push","Push"]
- 输入
- target=[1,2], n=4
- 输出
- ["Push","Push"]
最优解：一步一步想明白
- 3记牢一句:数在 target 里就 Push 留下,不在就 Push 再 Pop 弹走,栈等于 target 就停。下面每帧都在套这句。
- 4开局栈是空的,一个操作都还没有。上面这排 1 到 6 就是整数流,只能按从左到右的顺序取。目标是让栈从底到顶变成 [2,4,6]。下面这根栈每 Push 一个数就长高一层,Pop 一个就矮一层。指针从第一个数开始往右走。
- 5指针移到整数流的 1。题目规定:只要你决定取这个数,就必须先把它 Push 进栈,没有「看一眼再决定取不取」这种选项。所以下一帧先把 1 压进去,压完再判断它该不该留。
- 6把 1 压入栈顶,栈现在从底到顶是 [1]。再看 1 该不该留:target 是 [2,4,6],1 不在 target 里,是个多余的数,下一帧要把它 Pop 掉。
- 7把刚压进去的 1 从栈顶 Pop 出来,栈又回到 空。对 1 这个多余的数,我们用了一对 Push 和 Pop:指针往前走了一格,但栈的内容没变。这正是「不需要的数,先压再弹」的代价。
- 8指针移到整数流的 2。题目规定:只要你决定取这个数,就必须先把它 Push 进栈,没有「看一眼再决定取不取」这种选项。所以下一帧先把 2 压进去,压完再判断它该不该留。
- 9把 2 压入栈顶,栈现在从底到顶是 [2]。再看 2 该不该留:target 是 [2,4,6],2 正是 target 里需要的数,留着不动,这个 Push 是有效的一步。
- 10留下 2 之后,栈从底到顶是 [2],正好等于 target 的前 1 个 [2],对得上。但还没凑齐 target 的全部 3 个,继续取下一个数。
- 11指针移到整数流的 3。题目规定:只要你决定取这个数,就必须先把它 Push 进栈,没有「看一眼再决定取不取」这种选项。所以下一帧先把 3 压进去,压完再判断它该不该留。
- 12把 3 压入栈顶,栈现在从底到顶是 [2,3]。再看 3 该不该留:target 是 [2,4,6],3 不在 target 里,是个多余的数,下一帧要把它 Pop 掉。
- 13把刚压进去的 3 从栈顶 Pop 出来,栈又回到 [2]。对 3 这个多余的数,我们用了一对 Push 和 Pop:指针往前走了一格,但栈的内容没变。这正是「不需要的数,先压再弹」的代价。
- 14指针移到整数流的 4。题目规定:只要你决定取这个数,就必须先把它 Push 进栈,没有「看一眼再决定取不取」这种选项。所以下一帧先把 4 压进去,压完再判断它该不该留。
- 15把 4 压入栈顶,栈现在从底到顶是 [2,4]。再看 4 该不该留:target 是 [2,4,6],4 正是 target 里需要的数,留着不动,这个 Push 是有效的一步。
- 16留下 4 之后,栈从底到顶是 [2,4],正好等于 target 的前 2 个 [2,4],对得上。但还没凑齐 target 的全部 3 个,继续取下一个数。
- 17指针移到整数流的 5。题目规定:只要你决定取这个数,就必须先把它 Push 进栈,没有「看一眼再决定取不取」这种选项。所以下一帧先把 5 压进去,压完再判断它该不该留。
- 18把 5 压入栈顶,栈现在从底到顶是 [2,4,5]。再看 5 该不该留:target 是 [2,4,6],5 不在 target 里,是个多余的数,下一帧要把它 Pop 掉。
- 19把刚压进去的 5 从栈顶 Pop 出来,栈又回到 [2,4]。对 5 这个多余的数,我们用了一对 Push 和 Pop:指针往前走了一格,但栈的内容没变。这正是「不需要的数,先压再弹」的代价。
- 20指针移到整数流的 6。题目规定:只要你决定取这个数,就必须先把它 Push 进栈,没有「看一眼再决定取不取」这种选项。所以下一帧先把 6 压进去,压完再判断它该不该留。
- 21把 6 压入栈顶,栈现在从底到顶是 [2,4,6]。再看 6 该不该留:target 是 [2,4,6],6 正是 target 里需要的数,留着不动,这个 Push 是有效的一步。
- 22留下 6 之后,栈从底到顶是 [2,4,6],正好等于 target 的前 3 个 [2,4,6],对得上。而且长度已经凑齐 3 个,栈完全等于 target,可以停手了。
- 23栈现在从底到顶是 [2,4,6],和 target 一模一样。按第三条规则,这一刻必须立即停止:不再从整数流取数,也不再做任何 Push 或 Pop。即便 n 比这更大、流里还有数,也一概不读了。
- 24回看整个过程,操作序列是 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
✓ 对：每取一个数都必须先 Push,不需要再紧跟一个 Pop 弹掉
规则规定「从流中选取下一个整数并将其推送到栈顶」,取数和 Push 是绑定的,没有「取了却不压」这种操作。所以多余的数只能先 Push 再 Pop,这一对操作都要写进答案
✗ 错：真的去维护一整个栈来逐一比对
✓ 对：target 严格递增,只要从 1 数到 target 末值,挨个判断在不在 target 里就行
因为整数流恰好按 1、2、3 升序来,留下的数天然拼成升序的 target,你能提前算出每个数该 Push 还是该 Push 再 Pop。参考代码连栈都没开,只用一个计数器,省掉 O(n) 的栈空间
✗ 错：误以为要一直取到第 n 个数
✓ 对：栈一旦等于 target 就立即停止,后面的数不再读
题目第三条规则写得很清楚:任何时刻栈等于 target 就停手。比如 target=[1,2]、n=4,取到 2 栈就等于 target 了,3 和 4 根本不读,答案只有两个 Push
完整代码（Python / C++ / Java）
Python
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 buildArray(self, target: List[int], n: int) -> List[str]:
ans = []
cur = 1
for x in target:
while cur < x:
ans.extend(["Push", "Pop"])
cur += 1
ans.append("Push")
cur += 1
return ansC++
#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<string> buildArray(vector<int>& target, int n) {
vector<string> ans;
int cur = 1;
for (int x : target) {
while (cur < x) {
ans.push_back("Push");
ans.push_back("Pop");
++cur;
}
ans.push_back("Push");
++cur;
}
return ans;
}
};Java
import java.util.*;
class Solution {
public List<String> buildArray(int[] target, int n) {
List<String> ans = new ArrayList<>();
int cur = 1;
for (int x : target) {
while (cur < x) {
ans.addAll(Arrays.asList("Push", "Pop"));
++cur;
}
ans.add("Push");
++cur;
}
return ans;
}
}复杂度
时间
O(n)
计数器 cur 从 1 单调走到 target 的最后一个值就停,中间每个数只处理一次,处理是常数操作,所以是线性的,精确说是 O(target 末值),不超过 O(n)
空间
O(1)
按峰值算额外空间:参考代码只用了一个计数器 cur,是常数。返回的操作序列长度最多约 2 乘 target 末值再减 target 长度,不超过 2 乘 n,属于题目要求的输出、不计入额外开销。动画里画的那个栈只是帮理解,代码并不真的维护它,所以额外空间是 O(1)
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 用栈操作构建数组 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
为什么代码里不需要真的用一个栈?+
因为 target 严格递增,整数流又恰好按 1、2、3 升序吐数,你能提前算出每个数的命运:在 target 里就留(一个 Push),不在就先 Push 再 Pop。留下的数天然按升序排成 target,根本不需要把它们真的存进一个栈再比对。维护栈只是帮你想清楚规则,真写代码时一个计数器就够,省掉了 O(n) 的栈空间。
操作序列最长能有多长?+
每个不需要的数贡献一对 Push、Pop 共两个操作,每个需要的数贡献一个 Push。最坏情况是 target 只有一个很大的值,比如 target=[n],要先把 1 到 n 减 1 全部 Push 再 Pop,最后 Push 这个 n,一共 2 乘以 n 减 1 再加 1 个操作,是 O(n) 量级。
题目给的 n 到底有什么用?+
n 只是保证整数流的范围够大、target 里每个值都不超过 n,让你一定取得到需要的数。算法本身只数到 target 的最后一个值就停了,用不到它之后的数,所以 n 在三份参考代码里甚至没出现在循环条件里。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄声线把 用栈操作构建数组 一步步讲透（全站 0 节语音精讲，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。