【LeetCode】用栈操作构建数组 Java 题解

作者：Albert

2022-10-16
北京
本文字数：1015 字
阅读完需：约 1 分钟

题目描述

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

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

"Push"：从 list 中读取一个新元素，并将其推入数组中。"Pop"：删除数组中的最后一个元素。如果目标数组构建完成，就停止读取更多元素。题目数据保证目标数组严格递增，并且只包含 1 到 n 之间的数字。

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

示例 1：
输入：target = [1,3], n = 3输出：["Push","Push","Pop","Push"]解释： 读取 1 并自动推入数组 -> [1]读取 2 并自动推入数组，然后删除它 -> [1]读取 3 并自动推入数组 -> [1,3]
示例 2：
输入：target = [1,2,3], n = 3输出：["Push","Push","Push"]
示例 3：
输入：target = [1,2], n = 4输出：["Push","Push"]解释：只需要读取前 2 个数字就可以停止。

复制代码

思路分析

今天的算法题目是数组类型题目。题目要求的是用栈操作构建数组。我们都知道栈是一种线性数据结构，栈的修改是按照后进先出的原则进行的，因此栈通常被称为是后进先出（last in first out）表，简称 LIFO 表。
分析题目，这里需要我们利用栈的性质，记录栈的操作名，来构建数组。由于数据是从 1 到 n 开始的，我们可以采用模拟的方式，依次读入每一个数据，然后判断是否和 target 数组中的元素相同，相同就是 Push, 不同就是先 Push 后 Pop。具体实现代码如下，供参考。

通过代码

class Solution {    public List<String> buildArray(int[] target, int n) {        List<String> ans = new ArrayList<>();        int m = target.length;        int j = 1;        for (int i = 0; i < m; i++) {            for (; j <= n; j++) {                if (target[i] == j) {                    ans.add("Push");                    j++;                    break;                } else {                    ans.add("Push");                    ans.add("Pop");                }            }        }
        return ans;    }}

复制代码

总结

上述算法的时间复杂度是 O(n),空间复杂度是 O(1)
这个题目本身不难，通过这个题目，我们主要了解栈的操作。栈在我们实际的应用中，使用较多的是 Deque, Deque 是双端队列，指一个可以在队首/队尾插入或删除元素的队列。开发中使用方便。
坚持算法每日一题，加油！我会继续更新，也欢迎算法爱好者一起交流学习。

发布于: 刚刚阅读数: 2

原文链接:【http://xie.infoq.cn/article/eb2cfd8e0cace2665555c3293】。文章转载请联系作者。