Skip to content

Instantly share code, notes, and snippets.

@giuseppe998e

giuseppe998e/nge.rs

Last active December 14, 2022 19:29
Show Gist options
  • Save giuseppe998e/2e64abd696c1c876f7a897aff1c272e2 to your computer and use it in GitHub Desktop.
Save giuseppe998e/2e64abd696c1c876f7a897aff1c272e2 to your computer and use it in GitHub Desktop.
Download ZIP

Revisions

  1. giuseppe998e revised this gist Dec 14, 2022. No changes.
  2. giuseppe998e created this gist Dec 14, 2022.
    22 changes: 22 additions & 0 deletions nge.rs
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,22 @@
    fn next_greater_elems<T: Copy + PartialOrd>(array: &[T]) -> Box<[Option<T>]> {
    let array_len = array.len();
    let mut stack = Vec::<usize>::with_capacity(array_len);
    let mut result = Vec::<Option<T>>::with_capacity(array_len);

    stack.push(0);
    result.push(None);

    for (index, element) in array.iter().enumerate().skip(1) {
    result.push(None);

    // Use "<=" for "Greater-Equal"
    while let Some(&stack_index) = stack.last().filter(|&&idx| array[idx] < *element) {
    result[stack_index] = Some(*element);
    stack.pop();
    }

    stack.push(index);
    }

    result.into_boxed_slice()
    }
    25 changes: 25 additions & 0 deletions pge.rs
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,25 @@
    fn previous_greater_elems<T: Copy + PartialOrd>(array: &[T]) -> Box<[Option<T>]> {
    let array_len = array.len();
    let mut stack = Vec::<usize>::with_capacity(array_len);
    let mut result = Vec::<Option<T>>::with_capacity(array_len);

    stack.push(0);
    result.push(None);

    for (index, element) in array.iter().enumerate().skip(1) {
    while stack
    .last()
    .filter(|&&idx| array[idx] <= *element) // Use "<" for "Greater-Equal"
    .is_some()
    {
    stack.pop();
    }

    let result_element = stack.last().map(|&idx| array[idx]);
    result.push(result_element);

    stack.push(index);
    }

    result.into_boxed_slice()
    }