题目描述
给你一个下标从 0 开始的字符串数组 words
,其中 words[i]
要么是一个字符串形式的正整数,要么是字符串 "prev"
。
我们从数组的开头开始遍历,对于 words
中的每个 "prev"
字符串,找到 words
中的 上一个遍历的整数,定义如下:
k
表示到当前位置为止的连续"prev"
字符串数目(包含当前字符串),令下标从 0 开始的 整数 数组nums
表示目前为止遍历过的所有整数,同时用nums_reverse
表示nums
反转得到的数组,那么当前"prev"
对应的 上一个遍历的整数 是nums_reverse
数组中下标为(k - 1)
的整数。- 如果
k
比目前为止遍历过的整数数目 更多,那么上一个遍历的整数为-1
。
请你返回一个整数数组,包含所有上一个遍历的整数。
样例
入:words = ["1","2","prev","prev","prev"]
输出:[2,1,-1]
解释:
对于下标为 2 处的 "prev",上一个遍历的整数是 2,
因为连续 "prev" 数目为 1,同时在数组 reverse_nums 中,第一个元素是 2。
对于下标为 3 处的 "prev",上一个遍历的整数是 1,
因为连续 "prev" 数目为 2,同时在数组 reverse_nums 中,第二个元素是 1。
对于下标为 4 处的 "prev",上一个遍历的整数是 -1,
因为连续 "prev" 数目为 3,但总共只遍历过 2 个整数。
输入:words = ["1","prev","2","prev","prev"]
输出:[1,2,1]
解释:
对于下标为 1 处的 "prev",上一个遍历的整数是 1。
对于下标为 3 处的 "prev",上一个遍历的整数是 2。
对于下标为 4 处的 "prev",上一个遍历的整数是 1,
因为连续 "prev" 数目为 2,同时在数组 reverse_nums 中,第二个元素是 1 。
限制
1 <= words.length <= 100
words[i] == "prev"
或1 <= int(words[i]) <= 100
。
算法
(模拟) $O(n)$
- 根据题意,维护遍历的整数数组 $nums$,以及连续 “prev” 的数目 $k$。
- 每次更新答案后,更新 $k$ 或者 $nums$。
时间复杂度
- 遍历数组一次,每次遍历仅需要常数的时间,故时间复杂度为 $O(n)$。
空间复杂度
- 需要 $O(n)$ 的额外空间存储 $nums$ 和答案。
C++ 代码
class Solution {
public:
vector<int> lastVisitedIntegers(vector<string>& words) {
vector<int> nums, ans;
int k = 0;
for (const auto &w : words) {
if (w == "prev") {
++k;
if (k > nums.size()) ans.push_back(-1);
else ans.push_back(nums[nums.size() - k]);
} else {
k = 0;
nums.push_back(stoi(w));
}
}
return ans;
}
};