My solution extension of Next Greater Element O(n)


  • 0
    S
    public class Solution {
        class Node {
            int value;
            int index;
            
            public Node(int value, int index) {
                this.value = value;
                this.index = index;
            }
        }
        
        public int[] nextGreaterElements(int[] nums) {
            int[] result = new int[nums.length];
            if(nums == null || nums.length == 0) {
                return result;
            }
            Arrays.fill(result, Integer.MAX_VALUE);
            Stack<Node> stack = new Stack<>();
            stack.push(new Node(nums[0], 0));
            for(int i=1; i<nums.length; i++) {
                int value = nums[i];
                while(!stack.isEmpty() && stack.peek().value < value) {
                    Node node = stack.pop();
                    result[node.index] = i; 
                }
                stack.push(new Node(value, i));
            }
            
    
            int front = 0;
            int end = nums.length-1;
            while(front < end) {
                while(nums[end] < nums[front]) {
                    if((nums.length-end+front+1) < Math.abs((result[end]-end))) {
                        result[end] = front;
                    }
                    end--;
                }
                front++;
            }
            
            for(int i=0; i<result.length; i++) {
                if(result[i] == Integer.MAX_VALUE) {
                    result[i] = -1;
                } else {
                    result[i] = nums[result[i]];
                }
            }
            
            return result;
            
        }
    }

Log in to reply
 

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