Short AC solution and Fast DP solution 45ms


  • 1
    S

    Short normal soltuion 200ms

    public int[] nextGreaterElements2(int[] nums) {
    	int  n = nums.length;
    	int[] res = new int[n];
    	for (int i = 0; i < n; i++) {
    		res[i] = -1;
    		for (int k = i+1; k < i + n; k++) {
    			if (nums[k%n] > nums[i]){
    				res[i] = nums[k%n];
    				break;
    			}
    		}
    	}
    	return res;
    }
    

    DP solution 45ms

    public int[] nextGreaterElements(int[] nums) {
    	int  n = nums.length;
    	int[] res = new int[n];
    	int[] dp = new int[n];
    	for (int i = 0; i < n; i++) {
    		int cur = nums[i];
    		res[i] = -1;
    		dp[i] = -1;
    		for (int j = i+1; j <n; j++) {
    			if (nums[j] > cur){
    				res[i] = nums[j];
    				dp[i] = j;
    				break;
    			}
    		}
    		if (dp[i] == -1){
    			if (cur < nums[0]) res[i] = nums[0];
    			else{
    				int k = 0;
    				while (cur >= res[k] && k < i) {
    					if (dp[k] == -1) break;
    					k = dp[k];
    				}
    				if (k<i && cur < res[k])
    					res[i] = res[k];
    			}
    		}
    	}
    	return res;
    }
    

Log in to reply
 

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