FilesExpand file tree

 master

/

NextGreaterElementI496.java

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

52 lines (49 loc) · 2.02 KB

 master

/

NextGreaterElementI496.java

Copy path

Top

File metadata and controls

• Code
• Blame

52 lines (49 loc) · 2.02 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

/**

* 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.

*

* Example 2:

* Input: nums1 = [2,4], nums2 = [1,2,3,4].

* Output: [3,-1]

* Explanation:

* For number 2 in the first array, the next greater number for it in the second array is 3.

* For number 4 in the first array, there is no next greater number for it in the second array, so output -1.

*

* Note:

* All elements in nums1 and nums2 are unique.

* The length of both nums1 and nums2 would not exceed 1000.

*/

public class NextGreaterElementI496 {

public int[] nextGreaterElement(int[] nums1, int[] nums2) {

if (nums1 == null || nums1.length == 0) return new int[0];

int[] res = new int[nums1.length];

Map<Integer, Integer> map = new HashMap<>();

Stack<Integer> stack = new Stack<>();

for (int i=0; i<nums2.length; i++) {

if (stack.isEmpty() || stack.peek() >= nums2[i]) {

stack.push(nums2[i]);

continue;

}

while (!stack.isEmpty() && stack.peek() < nums2[i]) {

map.put(stack.pop(), nums2[i]);

}

stack.push(nums2[i]);

}

for (int i=0; i<nums1.length; i++) {

res[i] = map.getOrDefault(nums1[i], -1);

}

return res;

}

}