build-an-array-with-stack-operations

java

python

python3

mysql

mssql

oraclesql

csharp

javascript

typescript

bash

swift

kotlin

dart

golang

ruby

scala

rust

racket

erlang

elixir

pythondata

postgresql

cangjie

Algorithms

You are given an integer array <code>target</code> and an integer <code>n</code>.

You have an empty stack with the two following operations:

<ul>
	<li><code>&quot;Push&quot;</code>: pushes an integer to the top of the stack.</li>
	<li><code>&quot;Pop&quot;</code>: removes the integer on the top of the stack.</li>
</ul>

You also have a stream of the integers in the range <code>[1, n]</code>.

Use the two stack operations to make the numbers in the stack (from the bottom to the top) equal to <code>target</code>. You should follow the following rules:

<ul>
	<li>If the stream of the integers is not empty, pick the next integer from the stream and push it to the top of the stack.</li>
	<li>If the stack is not empty, pop the integer at the top of the stack.</li>
	<li>If, at any moment, the elements in the stack (from the bottom to the top) are equal to <code>target</code>, do not read new integers from the stream and do not do more operations on the stack.</li>
</ul>

Return the stack operations needed to build <code>target</code> following the mentioned rules. If there are multiple valid answers, return any of them.

&nbsp;
Example 1:

<pre>
Input: target = [1,3], n = 3
Output: [&quot;Push&quot;,&quot;Push&quot;,&quot;Pop&quot;,&quot;Push&quot;]
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].
</pre>

Example 2:

<pre>
Input: target = [1,2,3], n = 3
Output: [&quot;Push&quot;,&quot;Push&quot;,&quot;Push&quot;]
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].
</pre>

Example 3:

<pre>
Input: target = [1,2], n = 4
Output: [&quot;Push&quot;,&quot;Push&quot;]
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.
</pre>

&nbsp;
Constraints:

<ul>
	<li><code>1 &lt;= target.length &lt;= 100</code></li>
	<li><code>1 &lt;= n &lt;= 100</code></li>
	<li><code>1 &lt;= target[i] &lt;= n</code></li>
	<li><code>target</code> is strictly increasing.</li>
</ul>

buildArray

Build an Array With Stack Operations

Minimum Operations to Collect Elements

minimum-operations-to-collect-elements

收集元素的最少操作次数

Stack

Array

Simulation

给你一个数组 <code>target</code> 和一个整数 <code>n</code>。每次迭代，需要从&nbsp; <code>list = { 1 , 2 , 3 ..., n }</code> 中依次读取一个数字。

请使用下述操作来构建目标数组 <code>target</code> ：

<ul>
	<li><code>"Push"</code>：从 <code>list</code> 中读取一个新元素， 并将其推入数组中。</li>
	<li><code>"Pop"</code>：删除数组中的最后一个元素。</li>
	<li>如果目标数组构建完成，就停止读取更多元素。</li>
</ul>

题目数据保证目标数组严格递增，并且只包含 <code>1</code> 到 <code>n</code> 之间的数字。

请返回构建目标数组所用的操作序列。如果存在多个可行方案，返回任一即可。

&nbsp;

示例 1：

<pre>
输入：target = [1,3], n = 3
输出：["Push","Push","Pop","Push"]
解释： 
读取 1 并自动推入数组 -&gt; [1]
读取 2 并自动推入数组，然后删除它 -&gt; [1]
读取 3 并自动推入数组 -&gt; [1,3]
</pre>

示例 2：

<pre>
输入：target = [1,2,3], n = 3
输出：["Push","Push","Push"]
</pre>

示例 3：

<pre>
输入：target = [1,2], n = 4
输出：["Push","Push"]
解释：只需要读取前 2 个数字就可以停止。
</pre>

&nbsp;

提示：

<ul>
	<li><code>1 &lt;= target.length &lt;= 100</code></li>
	<li><code>1 &lt;= n &lt;= 100</code></li>
	<li><code>1 &lt;= target[i] &lt;= n</code></li>
	<li><code>target</code> 严格递增</li>
</ul>