0496. 下一个更大元素 I Next Greater Element I

问题描述

暴力法

思路比较简单:

• 遍历 nums1 数组中的所有元素, 当前元素为 x
• 遍历 nums2 数组中的所有元素, 找到第一个与 x 相等的元素, 然后向右继续遍历, 找到第一个比 x 大的元素

这个算法的时间复杂度是 O(n^2).

算法实现如下:

#![allow(unused)]
fn main() {
/// Brute force
pub fn next_greater_element1(nums1: Vec<i32>, nums2: Vec<i32>) -> Vec<i32> {
    // 用于记录每次遍历时的状态.
    #[derive(Debug, Default, Clone, Copy, Eq, PartialEq)]
    enum State {
        /// 没有找到相等的值
        #[default]
        NotFound,
        /// 找到了相等的值
        FoundEqual,
        /// 找到了相等的值, 同时在它的右侧也找到了更大的值
        FoundGreater,
    }

    let mut out = Vec::with_capacity(nums1.len());
    for x in nums1 {
        let mut state = State::NotFound;
        for &y in &nums2 {
            if state == State::NotFound && y == x {
                state = State::FoundEqual;
            }
            if state == State::FoundEqual && y > x {
                out.push(y);
                state = State::FoundGreater;
            }
        }
        if state != State::FoundGreater {
            out.push(-1);
        }
    }
    out
}
}

单调栈

因为要在 nums2 数组中找到当前元素, 以及当前元素右侧第一个更大的元素, 这个比较符合单调栈的操作.

具体操作是:

• 先遍历数组 nums2, 构造单调递增栈; 同时创建一个哈稀表, 用于存储 (当前元素值, 当前元素右侧第一个大的元素值) 映射关系 map
  • 如果当前元素比栈顶元素小, 直接入栈
  • 否则说明当前元素比栈顶元素大, 依次将栈顶元素出栈, 并存入 map 中. 这个栈顶元素的右侧第一个大的元素值就是当前元素
• 之后遍历 nums1 数组, 从 map 哈稀表中找到对应的更大的元素, 如果没有的话, 就存储为 -1

算法实现如下:

#![allow(unused)]
fn main() {
use std::collections::HashMap;

/// 使用单调栈
pub fn next_greater_element2(nums1: Vec<i32>, nums2: Vec<i32>) -> Vec<i32> {
    let mut monotonic_stack = Vec::with_capacity(nums2.len());
    assert!(!nums2.is_empty());
    let mut max_num = i32::MAX;
    let mut map = HashMap::new();

    // 构造递增式单调栈
    for &num in &nums2 {
        if num < max_num {
            // 将较小的元素入栈
            max_num = num;
            monotonic_stack.push(num);
        } else {
            // 将较小的元素出栈
            while !monotonic_stack.is_empty() && monotonic_stack[monotonic_stack.len() - 1] < num {
                let top = monotonic_stack.pop().unwrap();
                map.insert(top, num);
            }
            // 将当前元素入栈
            monotonic_stack.push(num);
        }
    }

    let out = nums1
        .iter()
        .map(|num1| map.get(num1).copied().unwrap_or(-1))
        .collect();

    out
}
}

C++ 实现如下:

#include <cassert>
#include <climits>

#include <iostream>
#include <stack>
#include <string>
#include <unordered_map>
#include <vector>

std::vector<int> nextGreaterElement(std::vector<int>& nums1, std::vector<int>& nums2) {
  std::stack<int> monotonic_stack;
  std::unordered_map<int, int> map;
  int max_num = INT_MAX;

  // 构造递增式单调栈
  for (int num2 : nums2) {
    if (num2 < max_num) {
      // 将较小的元素入栈
      max_num = num2;
      monotonic_stack.push(num2);
    } else {
      // 将较小的元素出栈
      while (!monotonic_stack.empty() && monotonic_stack.top() < num2) {
        const int top = monotonic_stack.top();
        monotonic_stack.pop();
        map.emplace(top, num2);
      }
      // 将当前元素入栈
      monotonic_stack.push(num2);
    }
  }

  std::vector<int> out;
  for (int num1 : nums1) {
    auto iter = map.find(num1);
    if (iter == map.cend()) {
      out.push_back(-1);
    } else {
      out.push_back(iter->second);
    }
  }

  return out;
}

void checkSolution() {
  {
    std::vector<int> nums1 = {4, 1, 2};
    std::vector<int> nums2 = {1, 3, 4, 2};
    std::vector<int> expected = {-1, 3, -1};
    assert(nextGreaterElement(nums1, nums2) == expected);
  }

  {
    std::vector<int> nums1 = {2, 4};
    std::vector<int> nums2 = {1, 2, 3, 4};
    std::vector<int> expected = {3, -1};
    assert(nextGreaterElement(nums1, nums2) == expected);
  }

  {
    std::vector<int> nums1 = {1, 3, 5, 2, 4};
    std::vector<int> nums2 = {6, 5, 4, 3, 2, 1, 7};
    std::vector<int> expected = {7, 7, 7, 7, 7};
    assert(nextGreaterElement(nums1, nums2) == expected);
  }
}

int main() {
  checkSolution();

  return 0;
}