Java beats 97% O(n) with stack


  • 0
    F

    public class Solution {
    public int[] nextGreaterElements(int[] nums) {
    if(nums == null || nums.length == 0) {
    return nums;
    }
    if(nums.length == 1) {
    nums[0] = -1;
    return nums;
    }
    Deque<Integer> dq = new ArrayDeque<Integer>();
    int max = Integer.MIN_VALUE;
    for(int i = nums.length - 1; i >= 0; i--) {
    max = Math.max(nums[i], max);
    if(i != nums.length - 1) {
    dq.addLast(nums[i]);
    }
    }
    int[] res = new int[nums.length];
    for(int i = nums.length - 1; i >= 0; i--) {
    int cur = nums[i];
    if(cur == max){
    dq.addLast(cur);
    res[i] = -1;
    } else{
    while(!dq.isEmpty() && cur >= dq.getLast()) {
    dq.removeLast();
    }
    res[i] = dq.getLast();
    dq.addLast(cur);
    }
    }
    return res;
    }
    }

    • list item

Log in to reply
 

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