Top 100
Next Greater Element II
- Problem
- LC 503
- File
- top100_LC503NextGreaterElementII.java
- Path
- pkg5leetcode/top100/top100_LC503NextGreaterElementII.java
- Package
- pkg5leetcode.top100
- Command
- java pkg5leetcode/top100/top100_LC503NextGreaterElementII.java
- Approach
- Monotonic stack on circular array (double scan).
- Complexity
- Time O(n), Space O(n)
There is no in-browser runner. This is the file from the curriculum, unchanged.
1package pkg5leetcode.top100;2 3/*4 * Next Greater Element II | LC 5035 * APPROACH: Monotonic stack on circular array (double scan).6 * COMPLEXITY: Time O(n), Space O(n)7 */8import java.util.*;9 10public class top100_LC503NextGreaterElementII {11 static int[] nextGreaterElements(int[] nums) {12 int n = nums.length;13 int[] res = new int[n];14 Arrays.fill(res, -1);15 Deque<Integer> st = new ArrayDeque<>();16 for (int i = 0; i < 2 * n; i++) {17 int idx = i % n;18 while (!st.isEmpty() && nums[st.peek()] < nums[idx]) res[st.pop()] = nums[idx];19 if (i < n) st.push(idx);20 }21 return res;22 }23 24 public static void main(String[] args) {25 check(java.util.Arrays.equals(nextGreaterElements(new int[]{1, 2, 1}), new int[]{2, -1, 2}), "case1");26 check(java.util.Arrays.equals(nextGreaterElements(new int[]{1, 2, 3, 4, 3}), new int[]{2, 3, 4, -1, 4}), "case2");27 System.out.println("all tests passed");28 }29 30 static void check(boolean cond, String name) {31 if (!cond) throw new AssertionError("FAILED: " + name);32 System.out.println(" PASS " + name);33 }34}