21ms Java Solution beats 99.84% with comments and explanations


  • 1
    L

    summary:
    find first occurance of the greatest element, set maxIndex= its index.

    declare an array holds the index of next greater element, set index[maxIndex]=-1.Then calculate each the other elements from right to left. Assuming we're calculating index[i], so we've calculated index[i+1], index[i+2].... There're two situations:

    1. nums[i]<nums[i+1]. Just set index[i] = i+1 (leave alone mod operations...)
    2. nums[i] >= nums[i+1]. We already known that the next element whose value greater than nums[i+1] stored in index[i+1], we can retrieve that greater value and compare to see if it is greater than nums[i]. If so, set index[i] = index[i+1]. Otherwise, repeat the process. (Proof: nums[i]>nums[i+1] and the closest greater element locates in nums[index[i+1]], so elements between nums[i+1]...nums[index[i+1]-1] are smaller than nums[i+1] so smaller than nums[i] appearantly, so we don't have to compare them one by one in linear search, which skips serval elements and makes the algorithm more efficient.)

    Then declare another array to store the result, loop and set result[i]=nums[index[i]]

    public class Solution {
        public int[] nextGreaterElements(int[] nums) {
            if (nums==null||nums.length==0) return new int[0];
            int maxIndex = 0;
            for (int i = 0; i < nums.length; i++) {
                if (nums[i] > nums[maxIndex]) {
                    maxIndex = i;  //find the largest element
                }
            }  
            int[] index = new int[nums.length]; //declare an array that holds the index of next greater element
            index[maxIndex] = -1; //set the max element's value to -1
            for (int i = (maxIndex - 1 + nums.length) % nums.length; i != maxIndex; i = (i - 1 + nums.length) % nums.length) { //the array is circular. pay attention to 'i'
                if (nums[i] < nums[(i + 1) % nums.length]) {
                    index[i] = (i + 1) % nums.length; //set index[i] = (i+1)%nums.length if index[(i+1)%nums.length]>index[i]
                } else {
                    int res = index[(i + 1 + nums.length) % nums.length]; //res = index of the cloest element whose value greater than nums[(i+1)%nums.length]
                    while (res != -1 && index[res] != -1 && nums[i] >= nums[res]) {  //find the closet index makes nums[index] > nums[i]
                        res = index[res]; //if nums[i] >= nums[res], try nums[index[res]], index[res] is the index of the closest element whose value is greater than nums[res]. repeat the process until we find such an element. 
                    }
                    if (res != -1 && nums[res] == nums[i]) { //res==-1 or index[res]==-1 means current element is another largest element, just set index[i] = -1.
                        res = -1;
                    }
                    index[i] = res;
                }
            }
            int[] result = new int[nums.length]; // retrieve value with index recorded previously
            for (int i = 0; i < result.length; i++) {
                int temp = index[i] != -1 ? nums[index[i]] : -1;
                result[i] = temp;
            }
            return result;
        }
    }
    

  • 0

    This is a nice algorithm. It is the first one I found here that does not achieve acceleration simply by modifying the Stack-based (decreasing subsequence based) algorithm. I also learned a lot just by reading how you write code. Thank you, and I am following you.


Log in to reply
 

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