Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commit6933963

Browse files
add a solution for 496
1 parent922fa18 commit6933963

File tree

2 files changed

+42
-10
lines changed

2 files changed

+42
-10
lines changed

‎src/main/java/com/fishercoder/solutions/_496.java

Lines changed: 38 additions & 10 deletions
Original file line numberDiff line numberDiff line change
@@ -1,29 +1,57 @@
11
packagecom.fishercoder.solutions;
22

3+
importjava.util.Deque;
34
importjava.util.HashMap;
5+
importjava.util.LinkedList;
46
importjava.util.Map;
57
importjava.util.Stack;
68

79
publicclass_496 {
810

911
publicstaticclassSolution1 {
10-
publicint[]nextGreaterElement(int[]findNums,int[]nums) {
11-
Stack<Integer>stack =newStack();
12+
publicint[]nextGreaterElement(int[]nums1,int[]nums2) {
13+
int[]ans =newint[nums1.length];
14+
Map<Integer,Integer>map =newHashMap<>();
15+
for (inti =0;i <nums2.length;i++) {
16+
map.put(nums2[i],i);
17+
}
18+
for (inti =0;i <nums1.length;i++) {
19+
intstart =map.get(nums1[i]);
20+
for (intj =start +1;j <nums2.length;j++) {
21+
if (nums2[j] >nums1[i]) {
22+
ans[i] =nums2[j];
23+
break;
24+
}
25+
}
26+
if (ans[i] ==0) {
27+
ans[i] = -1;
28+
}
29+
}
30+
returnans;
31+
}
32+
}
33+
34+
publicstaticclassSolution2 {
35+
/**
36+
* Use monotonic stack, using a pen and paper to help visualize this is a great help!
37+
*/
38+
publicint[]nextGreaterElement(int[]nums1,int[]nums2) {
39+
Deque<Integer>stack =newLinkedList<>();
1240
Map<Integer,Integer>map =newHashMap();
13-
for (inti =0;i <nums.length;i++) {
14-
while (!stack.isEmpty() &&nums[i] >stack.peek()) {
15-
map.put(stack.pop(),nums[i]);
41+
for (inti =0;i <nums2.length;i++) {
42+
while (!stack.isEmpty() &&nums2[i] >stack.peekLast()) {
43+
map.put(stack.pollLast(),nums2[i]);
1644
}
17-
stack.push(nums[i]);
45+
stack.addLast(nums2[i]);
1846
}
1947

2048
while (!stack.isEmpty()) {
21-
map.put(stack.pop(), -1);
49+
map.put(stack.pollLast(), -1);
2250
}
2351

24-
int[]result =newint[findNums.length];
25-
for (inti =0;i <findNums.length;i++) {
26-
result[i] =map.get(findNums[i]);
52+
int[]result =newint[nums1.length];
53+
for (inti =0;i <nums1.length;i++) {
54+
result[i] =map.get(nums1[i]);
2755
}
2856
returnresult;
2957
}

‎src/test/java/com/fishercoder/_496Test.java

Lines changed: 4 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -9,6 +9,7 @@
99

1010
publicclass_496Test {
1111
privatestatic_496.Solution1solution1;
12+
privatestatic_496.Solution2solution2;
1213
privatestaticint[]findNums;
1314
privatestaticint[]nums;
1415
privatestaticint[]expected;
@@ -17,6 +18,7 @@ public class _496Test {
1718
@BeforeClass
1819
publicstaticvoidsetup() {
1920
solution1 =new_496.Solution1();
21+
solution2 =new_496.Solution2();
2022
}
2123

2224
@Before
@@ -34,5 +36,7 @@ public void test1() {
3436
expected =newint[]{-1,3, -1};
3537
actual =solution1.nextGreaterElement(findNums,nums);
3638
assertArrayEquals(expected,actual);
39+
actual =solution2.nextGreaterElement(findNums,nums);
40+
assertArrayEquals(expected,actual);
3741
}
3842
}

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp