Java C++ 栈操作构建数组

时间:2022-10-20 AnjaVon 人气:0

题目要求

思路：模拟【双指针】

按题意模拟即可：

一个指针cur依次指向target中的每个元素，另一个指针i依次指向1∼n的数字；

对i所指向的每个数字进行Push操作，然后判断当前数字与target[cur]是否相等；

相等则判断下一个数字，同时将cur指向下一个元素；
否则需进行Pop操作。

过程中需注意cur的越界，当其越界则target构造完毕。

Java

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

时间复杂度：O(n)
空间复杂度：O(1)

C++

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

时间复杂度：O(n)
空间复杂度：O(1)

Rust

impl Solution {
    pub fn build_array(target: Vec<i32>, n: i32) -> Vec<String> {
        let mut res = Vec::new();
        let mut cur = 0;
        for i in 1..(n + 1) {
            if (cur < target.len()) {
                res.push(String::from("Push"));
                if (target[cur] != i) {
                    res.push(String::from("Pop"));
                }
                else {
                    cur += 1;
                }
            }          
        }
        res
    }
}

时间复杂度：O(n)
空间复杂度：O(1)

加载全部内容