54-用栈操作构建数组

自己的做法

算法思想

i从1到n循环。同时维持target的索引index，index初始为0。res结果数组初始为空

当i == target[i]时，res添加字符串"Push"，同时index 加1，判断index是否等于target长度size，如果等于， 结束循环。

如果i != target[i],即i这个值，在target数组中不存在，那么就应该先入栈再出栈，向res中依次添 加"Push"和"Pop"。

算法实现

class Solution {
public:
    vector<string> buildArray(vector<int>& target, int n) {
        int size = target.size();
        int index = 0;
        vector<string> res;
        for(int i = 1; i <= n; i++) {
            if(target[index] == i) {
                res.push_back("Push");
                index++;
                if(index == size) {
                    break;
                }
            } else {
                res.push_back("Push");
                res.push_back("Pop");
            }
        }
        return res;
    }
};

性能分析

时间复杂度：$O(n)$，n就是参数n。

空间复杂度：$O(1)$。结果数组不计入空间复杂度。

无参考做法。