add a solution for 496

fishercoder1534 · fishercoder1534 · commit 693396397400 · 2021-10-19T07:41:37.000-07:00
diff --git a/src/main/java/com/fishercoder/solutions/_496.java b/src/main/java/com/fishercoder/solutions/_496.java
@@ -1,29 +1,57 @@
 package com.fishercoder.solutions;
 
+import java.util.Deque;
 import java.util.HashMap;
+import java.util.LinkedList;
 import java.util.Map;
 import java.util.Stack;
 
 public class _496 {
 
     public static class Solution1 {
-        public int[] nextGreaterElement(int[] findNums, int[] nums) {
-            Stack<Integer> stack = new Stack();
+        public int[] nextGreaterElement(int[] nums1, int[] nums2) {
+            int[] ans = new int[nums1.length];
+            Map<Integer, Integer> map = new HashMap<>();
+            for (int i = 0; i < nums2.length; i++) {
+                map.put(nums2[i], i);
+            }
+            for (int i = 0; i < nums1.length; i++) {
+                int start = map.get(nums1[i]);
+                for (int j = start + 1; j < nums2.length; j++) {
+                    if (nums2[j] > nums1[i]) {
+                        ans[i] = nums2[j];
+                        break;
+                    }
+                }
+                if (ans[i] == 0) {
+                    ans[i] = -1;
+                }
+            }
+            return ans;
+        }
+    }
+
+    public static class Solution2 {
+        /**
+         * Use monotonic stack, using a pen and paper to help visualize this is a great help!
+         */
+        public int[] nextGreaterElement(int[] nums1, int[] nums2) {
+            Deque<Integer> stack = new LinkedList<>();
             Map<Integer, Integer> map = new HashMap();
-            for (int i = 0; i < nums.length; i++) {
-                while (!stack.isEmpty() && nums[i] > stack.peek()) {
-                    map.put(stack.pop(), nums[i]);
+            for (int i = 0; i < nums2.length; i++) {
+                while (!stack.isEmpty() && nums2[i] > stack.peekLast()) {
+                    map.put(stack.pollLast(), nums2[i]);
                 }
-                stack.push(nums[i]);
+                stack.addLast(nums2[i]);
             }
 
             while (!stack.isEmpty()) {
-                map.put(stack.pop(), -1);
+                map.put(stack.pollLast(), -1);
             }
 
-            int[] result = new int[findNums.length];
-            for (int i = 0; i < findNums.length; i++) {
-                result[i] = map.get(findNums[i]);
+            int[] result = new int[nums1.length];
+            for (int i = 0; i < nums1.length; i++) {
+                result[i] = map.get(nums1[i]);
             }
             return result;
         }
diff --git a/src/test/java/com/fishercoder/_496Test.java b/src/test/java/com/fishercoder/_496Test.java
@@ -9,6 +9,7 @@
 
 public class _496Test {
     private static _496.Solution1 solution1;
+    private static _496.Solution2 solution2;
     private static int[] findNums;
     private static int[] nums;
     private static int[] expected;
@@ -17,6 +18,7 @@ public class _496Test {
     @BeforeClass
     public static void setup() {
         solution1 = new _496.Solution1();
+        solution2 = new _496.Solution2();
     }
 
     @Before
@@ -34,5 +36,7 @@ public void test1() {
         expected = new int[]{-1, 3, -1};
         actual = solution1.nextGreaterElement(findNums, nums);
         assertArrayEquals(expected, actual);
+        actual = solution2.nextGreaterElement(findNums, nums);
+        assertArrayEquals(expected, actual);
     }
 }
