496.Next-Greater-Element-I

496. Next Greater Element I

้ข˜็›ฎๅœฐๅ€

https://leetcode.com/problems/next-greater-element-i/

้ข˜็›ฎๆ่ฟฐ

You are given two arrays (without duplicates) nums1 and nums2 where nums1โ€™s elements are subset of nums2. Find all the next greater numbers for nums1's elements in the corresponding places of nums2.

The Next Greater Number of a number x in nums1 is the first greater number to its right in nums2. If it does not exist, output -1 for this number.

Example 1:
Input: nums1 = [4,1,2], nums2 = [1,3,4,2].
Output: [-1,3,-1]
Explanation:
    For number 4 in the first array, you cannot find the next greater number for it in the second array, so output -1.
    For number 1 in the first array, the next greater number for it in the second array is 3.
    For number 2 in the first array, there is no next greater number for it in the second array, so output -1.

ไปฃ็ 

Approach #1 Brute Force

Complexity Analysis:

  • Time complexity: O(m * n)

  • Space complexity: O(m)

class Solution {
    public int[] nextGreaterElement(int[] findNums, int[] nums) {
    int[] res = new int[findNums.length];
    int j;
    for (int i = 0; i < findNums.length; i++) {
      boolean found = false;
      for (j = 0; j < nums.length; j++) {
        if (found && nums[j] > findNums[i]) {
          res[i] = nums[j];
          break;
        }
        if (nums[j] == findNums[i]) {
          found = true;
        }
      }
      if (j == nums.length) {
        res[i] = -1;
      }
    }

    return res;
  }

}

Approach #2 Better Brute Force

class Solution {
    public int[] nextGreaterElement(int[] findNums, int[] nums) {
        HashMap < Integer, Integer > hash = new HashMap < > ();
        int[] res = new int[findNums.length];
        int j;
        for (int i = 0; i < nums.length; i++) {
            hash.put(nums[i], i);
        }
        for (int i = 0; i < findNums.length; i++) {
            for (j = hash.get(findNums[i]) + 1; j < nums.length; j++) {

                if (findNums[i] < nums[j]) {
                    res[i] = nums[j];
                    break;
                }
            }
            if (j == nums.length) {
                res[i] = -1;
            }
        }
        return res;
    }
}

Approach #3 Using Stack and HashMap

Complexity Analysis

  • Time complexity : O(m+n). The entire nums array(of size n) is scanned only once. The stack's n elements are popped only once. The findNums array is also scanned only once.

  • Space complexity : O(m+n). stack and map of size n is used. res array of size mm is used, where nn refers to the length of the nums array and mm refers to the length of the findNums array.

class Solution {
  public int[] nextGeneraterElement(int[] findNums, int[] nums) {
    Stack<Integer> stack = new Stack<>();
    HashMap<Integer, Integer> map = new HashMap<>();
    int[] res = new int[findNums.length];
    for (int i = 0; i < nums.length; i++) {
      // ๅ•่ฐƒ้€’ๅ‡ๆ ˆ
      while (!stack.empty() && nums[i] > stack.peek()) {
        int small = stack.pop();
        map.put(small, nums[i]);
      }
      stack.push(nums[i]);
    }

    while (!stack.empty()) {
      map.put(stack.pop(), -1);
    }

    for (int i = 0; i < findNums.length; i++) {
      res[i] = map.get(findNums[i]);
    }

    return res;
  }
}

Last updated