Stack
Array
Hash Table
Monotonic Stack
Description
The next greater element of some element x
in an array is the first greater element that is to the right of x
in the same array.
You are given two distinct 0-indexed integer arrays nums1
and nums2
, where nums1
is a subset of nums2
.
For each 0 <= i < nums1.length
, find the index j
such that nums1[i] == nums2[j]
and determine the next greater element of nums2[j]
in nums2
. If there is no next greater element, then the answer for this query is -1
.
Return an array ans
of length nums1.length
such that ans[i]
is the next greater element as described above.
Example 1:
Input: nums1 = [4,1,2], nums2 = [1,3,4,2]
Output: [-1,3,-1]
Explanation: The next greater element for each value of nums1 is as follows:
- 4 is underlined in nums2 = [1,3,4 ,2]. There is no next greater element, so the answer is -1.
- 1 is underlined in nums2 = [1 ,3,4,2]. The next greater element is 3.
- 2 is underlined in nums2 = [1,3,4,2 ]. There is no next greater element, so the answer is -1.
Example 2:
Input: nums1 = [2,4], nums2 = [1,2,3,4]
Output: [3,-1]
Explanation: The next greater element for each value of nums1 is as follows:
- 2 is underlined in nums2 = [1,2 ,3,4]. The next greater element is 3.
- 4 is underlined in nums2 = [1,2,3,4 ]. There is no next greater element, so the answer is -1.
Constraints:
1 <= nums1.length <= nums2.length <= 1000
0 <= nums1[i], nums2[i] <= 104
All integers in nums1
and nums2
are unique .
All the integers of nums1
also appear in nums2
.
Follow up: Could you find an O(nums1.length + nums2.length)
solution?
Solutions
Solution 1
Python3 Java C++ Go TypeScript Rust JavaScript
class Solution :
def nextGreaterElement ( self , nums1 : List [ int ], nums2 : List [ int ]) -> List [ int ]:
m = {}
stk = []
for v in nums2 :
while stk and stk [ - 1 ] < v :
m [ stk . pop ()] = v
stk . append ( v )
return [ m . get ( v , - 1 ) for v in nums1 ]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18 class Solution {
public int [] nextGreaterElement ( int [] nums1 , int [] nums2 ) {
Deque < Integer > stk = new ArrayDeque <> ();
Map < Integer , Integer > m = new HashMap <> ();
for ( int v : nums2 ) {
while ( ! stk . isEmpty () && stk . peek () < v ) {
m . put ( stk . pop (), v );
}
stk . push ( v );
}
int n = nums1 . length ;
int [] ans = new int [ n ] ;
for ( int i = 0 ; i < n ; ++ i ) {
ans [ i ] = m . getOrDefault ( nums1 [ i ] , - 1 );
}
return ans ;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17 class Solution {
public :
vector < int > nextGreaterElement ( vector < int >& nums1 , vector < int >& nums2 ) {
stack < int > stk ;
unordered_map < int , int > m ;
for ( int & v : nums2 ) {
while ( ! stk . empty () && stk . top () < v ) {
m [ stk . top ()] = v ;
stk . pop ();
}
stk . push ( v );
}
vector < int > ans ;
for ( int & v : nums1 ) ans . push_back ( m . count ( v ) ? m [ v ] : -1 );
return ans ;
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20 func nextGreaterElement ( nums1 [] int , nums2 [] int ) [] int {
stk := [] int {}
m := map [ int ] int {}
for _ , v := range nums2 {
for len ( stk ) > 0 && stk [ len ( stk ) - 1 ] < v {
m [ stk [ len ( stk ) - 1 ]] = v
stk = stk [: len ( stk ) - 1 ]
}
stk = append ( stk , v )
}
var ans [] int
for _ , v := range nums1 {
val , ok := m [ v ]
if ! ok {
val = - 1
}
ans = append ( ans , val )
}
return ans
}
function nextGreaterElement ( nums1 : number [], nums2 : number []) : number [] {
const map = new Map < number , number > ();
const stack : number [] = [ Infinity ];
for ( const num of nums2 ) {
while ( num > stack [ stack . length - 1 ]) {
map . set ( stack . pop (), num );
}
stack . push ( num );
}
return nums1 . map ( num => map . get ( num ) || - 1 );
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18 use std :: collections :: HashMap ;
impl Solution {
pub fn next_greater_element ( nums1 : Vec < i32 > , nums2 : Vec < i32 > ) -> Vec < i32 > {
let mut map = HashMap :: new ();
let mut stack = Vec :: new ();
for num in nums2 {
while num > * stack . last (). unwrap_or ( & i32 :: MAX ) {
map . insert ( stack . pop (). unwrap (), num );
}
stack . push ( num );
}
nums1
. iter ()
. map ( | n | * map . get ( n ). unwrap_or ( &- 1 ))
. collect :: < Vec < i32 >> ()
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16 /**
* @param {number[]} nums1
* @param {number[]} nums2
* @return {number[]}
*/
var nextGreaterElement = function ( nums1 , nums2 ) {
let stk = [];
let m = {};
for ( let v of nums2 ) {
while ( stk && stk [ stk . length - 1 ] < v ) {
m [ stk . pop ()] = v ;
}
stk . push ( v );
}
return nums1 . map ( e => m [ e ] || - 1 );
};
Solution 2
Python3 Java C++ Go Rust JavaScript
class Solution :
def nextGreaterElement ( self , nums1 : List [ int ], nums2 : List [ int ]) -> List [ int ]:
m = {}
stk = []
for v in nums2 [:: - 1 ]:
while stk and stk [ - 1 ] <= v :
stk . pop ()
if stk :
m [ v ] = stk [ - 1 ]
stk . append ( v )
return [ m . get ( x , - 1 ) for x in nums1 ]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21 class Solution {
public int [] nextGreaterElement ( int [] nums1 , int [] nums2 ) {
Deque < Integer > stk = new ArrayDeque <> ();
Map < Integer , Integer > m = new HashMap <> ();
for ( int i = nums2 . length - 1 ; i >= 0 ; -- i ) {
while ( ! stk . isEmpty () && stk . peek () <= nums2 [ i ] ) {
stk . pop ();
}
if ( ! stk . isEmpty ()) {
m . put ( nums2 [ i ] , stk . peek ());
}
stk . push ( nums2 [ i ] );
}
int n = nums1 . length ;
int [] ans = new int [ n ] ;
for ( int i = 0 ; i < n ; ++ i ) {
ans [ i ] = m . getOrDefault ( nums1 [ i ] , - 1 );
}
return ans ;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15 class Solution {
public :
vector < int > nextGreaterElement ( vector < int >& nums1 , vector < int >& nums2 ) {
stack < int > stk ;
unordered_map < int , int > m ;
for ( int i = nums2 . size () - 1 ; ~ i ; -- i ) {
while ( ! stk . empty () && stk . top () <= nums2 [ i ]) stk . pop ();
if ( ! stk . empty ()) m [ nums2 [ i ]] = stk . top ();
stk . push ( nums2 [ i ]);
}
vector < int > ans ;
for ( int & v : nums1 ) ans . push_back ( m . count ( v ) ? m [ v ] : -1 );
return ans ;
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22 func nextGreaterElement ( nums1 [] int , nums2 [] int ) [] int {
stk := [] int {}
m := map [ int ] int {}
for i := len ( nums2 ) - 1 ; i >= 0 ; i -- {
for len ( stk ) > 0 && stk [ len ( stk ) - 1 ] <= nums2 [ i ] {
stk = stk [: len ( stk ) - 1 ]
}
if len ( stk ) > 0 {
m [ nums2 [ i ]] = stk [ len ( stk ) - 1 ]
}
stk = append ( stk , nums2 [ i ])
}
var ans [] int
for _ , v := range nums1 {
val , ok := m [ v ]
if ! ok {
val = - 1
}
ans = append ( ans , val )
}
return ans
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19 impl Solution {
pub fn next_greater_element ( nums1 : Vec < i32 > , nums2 : Vec < i32 > ) -> Vec < i32 > {
nums1
. iter ()
. map ( | target | {
let mut res = - 1 ;
for num in nums2 . iter (). rev () {
if num == target {
break ;
}
if num > target {
res = * num ;
}
}
res
})
. collect :: < Vec < i32 >> ()
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19 /**
* @param {number[]} nums1
* @param {number[]} nums2
* @return {number[]}
*/
var nextGreaterElement = function ( nums1 , nums2 ) {
let stk = [];
let m = {};
for ( let v of nums2 . reverse ()) {
while ( stk && stk [ stk . length - 1 ] <= v ) {
stk . pop ();
}
if ( stk ) {
m [ v ] = stk [ stk . length - 1 ];
}
stk . push ( v );
}
return nums1 . map ( e => m [ e ] || - 1 );
};