楼主:
Rushia (みけねこ的鼻屎)
2023-11-03 23:21:09https://leetcode.com/problems/build-an-array-with-stack-operations/description
1441. Build an Array With Stack Operations
给你一个阵列 target[] 和一个数字 n ,n 表示一个范围 1~n 的连续数字资料流,
我们可以对这个资料流做两个操作:
1.PUSH:从资料流取出一个资料放入结果集顶端,若取出 i 下次会 PUSH 出 i + 1。
2.POP:从结果集POP(移除顶端)一个资料。
求出要用什么样的顺序对结果集PUSH和POP可以得到TARGET。
* 题目保证一定存在至少一个合法的PUSH和POP顺序,若有多种可能只需返回其中一种。
* 结果集初始化为 []
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].
思路:
1.有Stack的观念然后就可以用双指针处理,每次固定从流PUSH一个元素到结果集。
2.如果顶端元素和target的当前元素相同,继续往后面匹配(移动指针),否则Pop
掉刚刚Push的元素。
3.上面的PUSH和POP过程保存起来,做到指标走完target就可以结束(后面的流不用管)
Java Code: