#1441
Build an Array With Stack Operations
pupil · 470 · lc medium +26 · verified · 81% accepted · 1,220 likes · top 93%
Description
You have an empty stack supporting two operations: "Push" (add an integer to the top) and "Pop" (remove the top integer). A stream of integers from 1 to n is available in order.
Use these operations to build the array target from bottom to top, following these rules:
- If the stream is non-empty, pull the next integer and push it onto the stack.
- If the stack is non-empty, pop the top element.
- Stop as soon as the stack contents (bottom to top) match target.
Return any valid sequence of operation strings that achieves this. If multiple answers exist, any is acceptable.
Example 1:
Input: target = [1,3], n = 3
Output: ["Push","Push","Pop","Push"]
Explanation: Initially the stack s is empty. The last element is the top of the stack.
Read 1 from the stream and push it to the stack. s = [1].
Read 2 from the stream and push it to the stack. s = [1,2].
Pop the integer on the top of the stack. s = [1].
Read 3 from the stream and push it to the stack. s = [1,3].
Example 2:
Input: target = [1,2,3], n = 3
Output: ["Push","Push","Push"]
Explanation: Initially the stack s is empty. The last element is the top of the stack.
Read 1 from the stream and push it to the stack. s = [1].
Read 2 from the stream and push it to the stack. s = [1,2].
Read 3 from the stream and push it to the stack. s = [1,2,3].
Example 3:
Input: target = [1,2], n = 4
Output: ["Push","Push"]
Explanation: Initially the stack s is empty. The last element is the top of the stack.
Read 1 from the stream and push it to the stack. s = [1].
Read 2 from the stream and push it to the stack. s = [1,2].
Since the stack (from the bottom to the top) is equal to target, we stop the stack operations.
The answers that read integer 3 from the stream are not accepted.
Code
1
2
3