8000 refactor 503 · noodlesfate1/Leetcode-1@ea5c918 · GitHub
[go: up one dir, main page]
Skip to content

Commit ea5c918

Browse files
fishercoder1534fishercoder1534
committed
refactor 503
1 parent 0c3f651 commit ea5c918

File tree

2 files changed

+50
-35
lines changed

2 files changed

+50
-35
lines changed

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

Lines changed: 42 additions & 32 deletions
Original file line numberDiff line numberDiff line change
@@ -3,6 +3,8 @@
33
import java.util.Stack;
44

55
/**
6+
* 503. Next Greater Element II
7+
*
68
* Given a circular array (the next element of the last element is the first element of the array),
79
* print the Next Greater Number for every element.
810
* The Next Greater Number of a number x is the first greater number to its traversing-order next in the array,
@@ -18,45 +20,53 @@
1820
*/
1921
public class _503 {
2022

21-
//Credit: https://discuss.leetcode.com/topic/77881/typical-ways-to-solve-circular-array-problems-java-solution
22-
//Note: we store INDEX into the stack, reversely, the larger index put at the bottom of the stack, the smaller index at the top
23-
public int[] nextGreaterElements(int[] nums) {
24-
if (nums == null || nums.length == 0) {
25-
return nums;
26-
}
27-
int len = nums.length;
28-
Stack<Integer> stack = new Stack<>();
29-
for (int i = len - 1; i >= 0; i--) {
30-
stack.push(i);
31-
//push all indexes into the stack reversely
32-
}
33-
int[] result = new int[len];
34-
for (int i = len - 1; i >= 0; i--) {
35-
result[i] = -1;
36-
//initialize it to be -1 in case we cannot find its next greater element in the array
37-
while (!stack.isEmpty() && (nums[stack.peek()] <= nums[i])) {
38-
stack.pop();
23+
public static class Solution1 {
24+
/**
25+
* Credit: https://discuss.leetcode.com/topic/77881/typical-ways-to-solve-circular-array-problems-java-solution
26+
* Note: we store INDEX into the stack, reversely, the larger index put at the bottom of the stack, the smaller index at the top
27+
*/
28+
public int[] nextGreaterElements(int[] nums) {
29+
if (nums == null || nums.length == 0) {
30+
return nums;
31+
}
32+
int len = nums.length;
33+
Stack<Integer> stack = new Stack<>();
34+
for (int i = len - 1; i >= 0; i--) {
35+
stack.push(i);
36+
//push all indexes into the stack reversely
3937
}
40-
if (!stack.isEmpty()) {
41-
result[i] = nums[stack.peek()];
38+
int[] result = new int[len];
39+
for (int i = len - 1; i >= 0; i--) {
40+
result[i] = -1;
41+
//initialize it to be -1 in case we cannot find its next greater element in the array
42+
while (!stack.isEmpty() && (nums[stack.peek()] <= nums[i])) {
43+
stack.pop();
44+
}
45+
if (!stack.isEmpty()) {
46+
result[i] = nums[stack.peek()];
47+
}
48+
stack.push(i);
4249
}
43-
stack.push(i);
50+
return result;
4451
}
45-
return result;
4652
}
4753

48-
//credit: https://leetcode.com/articles/next-greater-element-ii/
49-
public int[] nextGreaterElements_editorial_solution(int[] nums) {
50-
int[] result = new int[nums.length];
51-
Stack<Integer> stack = new Stack<>();
52-
for (int i = nums.length * 2 - 1; i >= 0; i--) {
53-
while (!stack.isEmpty() && nums[stack.peek()] <= nums[i % nums.length]) {
54-
stack.pop();
54+
public static class Solution2 {
55+
/**
56+
* credit: https://leetcode.com/articles/next-greater-element-ii/
57+
*/
58+
public int[] nextGreaterElements(int[] nums) {
59+
int[] result = new int[nums.length];
60+
Stack<Integer> stack = new Stack<>();
61+
for (int i = nums.length * 2 - 1; i >= 0; i--) {
62+
while (!stack.isEmpty() && nums[stack.peek()] <= nums[i % nums.length]) {
63+
stack.pop();
64+
}
65+
result[i % nums.length] = stack.isEmpty() ? -1 : nums[stack.peek()];
66+
stack.push(i % nums.length);
5567
}
56-
result[i % nums.length] = stack.isEmpty() ? -1 : nums[stack.peek()];
57-
stack.push(i % nums.length);
68+
return result;
5869
}
59-
return result;
6070
}
6171

6272
}

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

Lines changed: 8 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -8,14 +8,16 @@
88
import static org.junit.Assert.assertArrayEquals;
99

1010
public class _503Test {
11-
private static _503 test;
11+
private static _503.Solution1 solution1;
12+
private static _503.Solution2 solution2;
1213
private static int[] nums;
131 67E6 4
private static int[] expected;
1415
private static int[] actual;
1516

1617
@BeforeClass
1718
public static void setup() {
18-
test = new _503();
19+
solution1 = new _503.Solution1();
20+
solution2 = new _503.Solution2();
1921
}
2022

2123
@Before
@@ -28,7 +30,10 @@ public void setupForEachTest() {
2830
public void test1() {
2931
nums = new int[]{1, 2, 1};
3032
expected = new int[]{2, -1, 2};
31-
actual = test.nextGreaterElements(nums);
33+
actual = solution1.nextGreaterElements(nums);
34+
assertArrayEquals(expected, actual);
35+
36+
actual = solution2.nextGreaterElements(nums);
3237
assertArrayEquals(expected, actual);
3338
}
3439
}

0 commit comments

Comments
 (0)
0