leetcode-1441:用栈操作构建数组

简介: leetcode-1441:用栈操作构建数组

题目

题目连接

给你一个数组 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 个数字就可以停止。

解题

方法一:

存在的数,直接Push

不存在的数,先Push,后Pop

class Solution {
public:
    vector<string> buildArray(vector<int>& target, int n) {
        int num=1;
        int i=0;
        vector<string> res;
        while(num<=n&&i<target.size()){
            if(num==target[i]){
                num++;
                i++;
                res.push_back("Push");
            }else{
                num++;
                res.push_back("Push");
                res.push_back("Pop");
            }
        }
        return res;
    }
};
相关文章
|
1月前
|
算法
Leetcode 初级算法 --- 数组篇
Leetcode 初级算法 --- 数组篇
37 0
|
27天前
【LeetCode-每日一题】 删除排序数组中的重复项
【LeetCode-每日一题】 删除排序数组中的重复项
18 4
|
26天前
|
索引
Leetcode第三十三题(搜索旋转排序数组)
这篇文章介绍了解决LeetCode第33题“搜索旋转排序数组”的方法,该问题要求在旋转过的升序数组中找到给定目标值的索引,如果存在则返回索引,否则返回-1,文章提供了一个时间复杂度为O(logn)的二分搜索算法实现。
16 0
Leetcode第三十三题(搜索旋转排序数组)
|
26天前
【LeetCode 24】225.用队列实现栈
【LeetCode 24】225.用队列实现栈
9 0
|
26天前
|
算法 C++
Leetcode第53题(最大子数组和)
这篇文章介绍了LeetCode第53题“最大子数组和”的动态规划解法,提供了详细的状态转移方程和C++代码实现,并讨论了其他算法如贪心、分治、改进动态规划和分块累计法。
50 0
|
26天前
|
算法
【LeetCode 23】232.用栈实现队列
【LeetCode 23】232.用栈实现队列
15 0
|
26天前
|
C++
【LeetCode 12】349.两个数组的交集
【LeetCode 12】349.两个数组的交集
15 0
|
3月前
|
算法
LeetCode第81题搜索旋转排序数组 II
文章讲解了LeetCode第81题"搜索旋转排序数组 II"的解法,通过二分查找算法并加入去重逻辑来解决在旋转且含有重复元素的数组中搜索特定值的问题。
LeetCode第81题搜索旋转排序数组 II
|
2月前
|
Unix Shell Linux
LeetCode刷题 Shell编程四则 | 194. 转置文件 192. 统计词频 193. 有效电话号码 195. 第十行
本文提供了几个Linux shell脚本编程问题的解决方案,包括转置文件内容、统计词频、验证有效电话号码和提取文件的第十行,每个问题都给出了至少一种实现方法。
LeetCode刷题 Shell编程四则 | 194. 转置文件 192. 统计词频 193. 有效电话号码 195. 第十行
|
3月前
|
搜索推荐 索引 Python
【Leetcode刷题Python】牛客. 数组中未出现的最小正整数
本文介绍了牛客网题目"数组中未出现的最小正整数"的解法,提供了一种满足O(n)时间复杂度和O(1)空间复杂度要求的原地排序算法,并给出了Python实现代码。
106 2