Commit9c3532f

committed

[LEET-000] add one more way for Next Greater Element I

1 parent9ddcb69 commit9c3532fCopy full SHA for 9c3532f

File tree

+29

-2

lines changed

leetcode-algorithms/src
- main/java/com/stevesun/solutions
  - NextGreaterElementI.java
- test/java/com/stevesun
  - NextGreaterElementITest.java

+29

-2

lines changed

Lines changed: 25 additions & 1 deletion

Original file line number	Diff line number	Diff line change
`@@ -1,5 +1,9 @@`
`1`	`1`	`packagecom.stevesun.solutions;`
`2`	`2`
	`3`	`+importjava.util.HashMap;`
	`4`	`+importjava.util.Map;`
	`5`	`+importjava.util.Stack;`
	`6`	`+`
`3`	`7`	`/**`
`4`	`8`	`* 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.`
`5`	`9`
`@@ -24,7 +28,27 @@`
`24`	`28`	`*/`
`25`	`29`	`publicclassNextGreaterElementI {`
`26`	`30`
`27`		`-publicint[]nextGreaterElement(int[]findNums,int[]nums) {`
	`31`	`+publicint[]nextGreaterElement_clever_way(int[]findNums,int[]nums) {`
	`32`	`+Stack<Integer>stack =newStack();`
	`33`	`+Map<Integer,Integer>map =newHashMap();`
	`34`	`+for (inti =0;i <nums.length;i++) {`
	`35`	`+while (!stack.isEmpty() &&nums[i] >stack.peek()) {`
	`36`	`+map.put(stack.pop(),nums[i]);`
	`37`	`+ }`
	`38`	`+stack.push(nums[i]);`
	`39`	`+ }`
	`40`	`+`
	`41`	`+while (!stack.isEmpty())map.put(stack.pop(), -1);`
	`42`	`+`
	`43`	`+int[]result =newint[findNums.length];`
	`44`	`+for (inti =0;i <findNums.length;i++) {`
	`45`	`+result[i] =map.get(findNums[i]);`
	`46`	`+ }`
	`47`	`+returnresult;`
	`48`	`+ }`
	`49`	`+`
	`50`	`+`
	`51`	`+publicint[]nextGreaterElement_naive_way(int[]findNums,int[]nums) {`
`28`	`52`	`int[]result =newint[findNums.length];`
`29`	`53`	`for (inti =0;i <findNums.length;i++) {`
`30`	`54`	`booleanfound =false;`

Lines changed: 4 additions & 1 deletion

Original file line number	Diff line number	Diff line change
`@@ -32,7 +32,10 @@ public void test1(){`
`32`	`32`	`findNums =newint[]{4,1,2};`
`33`	`33`	`nums =newint[]{1,3,4,2};`
`34`	`34`	`expected =newint[]{-1,3, -1};`
`35`		`-actual =test.nextGreaterElement(findNums,nums);`
	`35`	`+actual =test.nextGreaterElement_naive_way(findNums,nums);`
	`36`	`+assertArrayEquals(expected,actual);`
	`37`	`+`
	`38`	`+actual =test.nextGreaterElement_clever_way(findNums,nums);`
`36`	`39`	`assertArrayEquals(expected,actual);`
`37`	`40`	`}`
`38`	`41`	`}`

Comments

(0)