Question

2899. Last Visited Integers

中文文档

Description

Given an integer array nums where nums[i] is either a positive integer or -1.

We need to find for each -1 the respective positive integer, which we call the last visited integer.

To achieve this goal, let's define two empty arrays: seen and ans.

Start iterating from the beginning of the array nums.

• If a positive integer is encountered, prepend it to the front of seen.
• If -1 is encountered, let k be the number of consecutive -1s seen so far (including the current -1),
  • If k is less than or equal to the length of seen, append the k-th element of seen to ans.
  • If k is strictly greater than the length of seen, append -1 to ans.

Return _the array _ans.

 

Example 1:

Input: nums = [1,2,-1,-1,-1]

Output: [2,1,-1]

Explanation: Start with seen = [] and ans = [].

1. Process nums[0]: The first element in nums is 1. We prepend it to the front of seen. Now, seen == [1].
2. Process nums[1]: The next element is 2. We prepend it to the front of seen. Now, seen == [2, 1].
3. Process nums[2]: The next element is -1. This is the first occurrence of -1, so k == 1. We look for the first element in seen. We append 2 to ans. Now, ans == [2].
4. Process nums[3]: Another -1. This is the second consecutive -1, so k == 2. The second element in seen is 1, so we append 1 to ans. Now, ans == [2, 1].
5. Process nums[4]: Another -1, the third in a row, making k = 3. However, seen only has two elements ([2, 1]). Since k is greater than the number of elements in seen, we append -1 to ans. Finally, ans == [2, 1, -1].

Example 2:

Input: nums = [1,-1,2,-1,-1]

Output: [1,2,1]

Explanation: Start with seen = [] and ans = [].

1. Process nums[0]: The first element in nums is 1. We prepend it to the front of seen. Now, seen == [1].
2. Process nums[1]: The next element is -1. This is the first occurrence of -1, so k == 1. We look for the first element in seen, which is 1. Append 1 to ans. Now, ans == [1].
3. Process nums[2]: The next element is 2. Prepend this to the front of seen. Now, seen == [2, 1].
4. Process nums[3]: The next element is -1. This -1 is not consecutive to the first -1 since 2 was in between. Thus, k resets to 1. The first element in seen is 2, so append 2 to ans. Now, ans == [1, 2].
5. Process nums[4]: Another -1. This is consecutive to the previous -1, so k == 2. The second element in seen is 1, append 1 to ans. Finally, ans == [1, 2, 1].

 

Constraints:

• 1 <= nums.length <= 100
• nums[i] == -1 or 1 <= nums[i] <= 100

Solutions

Solution 1: Simulation

We can directly simulate according to the problem statement. In the implementation, we use an array $nums$ to store the traversed integers, and an integer $k$ to record the current number of consecutive $prev$ strings. If the current string is $prev$, we take out the $|nums| - k-th$ integer from $nums$. If it does not exist, we return $-1$.

The time complexity is $O(n)$, where $n$ is the length of the array $words$. The space complexity is $O(n)$.

class Solution:
  def lastVisitedIntegers(self, words: List[str]) -> List[int]:
    nums = []
    ans = []
    k = 0
    for w in words:
      if w == "prev":
        k += 1
        i = len(nums) - k
        ans.append(-1 if i < 0 else nums[i])
      else:
        k = 0
        nums.append(int(w))
    return ans

class Solution {
  public List<Integer> lastVisitedIntegers(List<String> words) {
    List<Integer> nums = new ArrayList<>();
    List<Integer> ans = new ArrayList<>();
    int k = 0;
    for (var w : words) {
      if ("prev".equals(w)) {
        ++k;
        int i = nums.size() - k;
        ans.add(i < 0 ? -1 : nums.get(i));
      } else {
        k = 0;
        nums.add(Integer.valueOf(w));
      }
    }
    return ans;
  }
}

class Solution {
public:
  vector<int> lastVisitedIntegers(vector<string>& words) {
    vector<int> nums;
    vector<int> ans;
    int k = 0;
    for (auto& w : words) {
      if (w == "prev") {
        ++k;
        int i = nums.size() - k;
        ans.push_back(i < 0 ? -1 : nums[i]);
      } else {
        k = 0;
        nums.push_back(stoi(w));
      }
    }
    return ans;
  }
};

func lastVisitedIntegers(words []string) (ans []int) {
  nums := []int{}
  k := 0
  for _, w := range words {
    if w == "prev" {
      k++
      i := len(nums) - k
      if i < 0 {
        ans = append(ans, -1)
      } else {
        ans = append(ans, nums[i])
      }
    } else {
      k = 0
      x, _ := strconv.Atoi(w)
      nums = append(nums, x)
    }
  }
  return
}

function lastVisitedIntegers(words: string[]): number[] {
  const nums: number[] = [];
  const ans: number[] = [];
  let k = 0;
  for (const w of words) {
    if (w === 'prev') {
      ++k;
      const i = nums.length - k;
      ans.push(i < 0 ? -1 : nums[i]);
    } else {
      k = 0;
      nums.push(+w);
    }
  }
  return ans;
}

impl Solution {
  pub fn last_visited_integers(words: Vec<String>) -> Vec<i32> {
    let mut nums: Vec<i32> = Vec::new();
    let mut ans: Vec<i32> = Vec::new();
    let mut k = 0;

    for w in words {
      if w == "prev" {
        k += 1;
        let i = (nums.len() as i32) - k;
        ans.push(if i < 0 { -1 } else { nums[i as usize] });
      } else {
        k = 0;
        nums.push(w.parse::<i32>().unwrap());
      }
    }

    ans
  }
}