Java 1pass O(n)time & O(n)space solution beats 99%


  • 2
    W
    public class Solution {
        public int[] nextGreaterElements(int[] nums) {
            int[] r = new int[nums.length];
            if(nums.length == 0) return r;
            Arrays.fill(r, -1);
            int[] N = new int[nums.length];
            int[] P = new int[nums.length]; 
            N[0] = nums[0];
            P[0] = 0;
            int p = 0, l = 2 * r.length;
            for(int i = 1; i < l - 1; ++i){
                int ri = i % r.length;
                if(nums[ri] <= N[p]){
                    if(++p >= r.length) break;
                    N[p] = nums[ri];
                    P[p] = ri;
                } else {
                    while(p >= 0 && N[p] < nums[ri]){
                        r[P[p]] = nums[ri];
                        --p;
                    }
                    N[++p] = nums[ri];
                    P[p] = ri;
                }
            }
            return r;
        }
    }
    

  • 0
    M

    Nice!

    I came to a similar solution but my code is not nearly as concise.

    This code beats 99.34%.

    public class Solution {
        public int[] nextGreaterElements(int[] nums) {
            if (nums.length == 0) return nums;
            int[] dp = new int[nums.length];
            int index = findMax(nums); 
            dp[index] = -1;
            int i=index-1;
            if (i < 0) i = nums.length-1;
            while (i != index) {
                findNext(dp, nums, i);
                i--; if (i < 0) i = nums.length-1;
            }
            for (int j=0; j<nums.length; j++) {
                dp[j] = (dp[j] == -1) ? -1 : nums[dp[j]];
            }
            return dp;
        }
        private void findNext(int[] dp, int[] nums, int i) {
            int j = (i+1) % nums.length;
            while (j != i) {
                if (j != -1 && nums[j] <= nums[i]){
                	j = dp[j];
                }
                else break;
            }
            dp[i] = j;
        }
        private int findMax(int[] nums) {
            int max = Integer.MIN_VALUE;
            int index = 0;
            for (int i=0; i<nums.length; i++) {
                if (nums[i] > max) {
                    index = i;
                    max = nums[i];
                }
            }
            return index;
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.