Java 10 lines and C++ 12 lines linear time complexity O(n) with explanation


  • 75
    Y

    The approach is same as Next Greater Element I
    See explanation in my solution to the previous problem
    The only difference here is that we use stack to keep the indexes of the decreasing subsequence

    Java

        public int[] nextGreaterElements(int[] nums) {
            int n = nums.length, next[] = new int[n];
            Arrays.fill(next, -1);
            Stack<Integer> stack = new Stack<>(); // index stack
            for (int i = 0; i < n * 2; i++) {
                int num = nums[i % n]; 
                while (!stack.isEmpty() && nums[stack.peek()] < num)
                    next[stack.pop()] = num;
                if (i < n) stack.push(i);
            }   
            return next;
        }
    

    C++

        vector<int> nextGreaterElements(vector<int>& nums) {
            int n = nums.size();
            vector<int> next(n, -1);
            stack<int> s; // index stack
            for (int i = 0; i < n * 2; i++) {
                int num = nums[i % n]; 
                while (!s.empty() && nums[s.top()] < num) {
                    next[s.top()] = num;
                    s.pop();
                }
                if (i < n) s.push(i);
            }   
            return next;
        }
    

  • 2

    Nice solution.
    We can also iterate from back to front and maintain a decreasing stack, this will reduce the times of updating result array.

    For Next Greater Element I:

    class Solution {
    public:
        vector<int> nextGreaterElement(vector<int>& findNums, vector<int>& nums) {
            if (findNums.empty()) return {};
            int n = nums.size();
            unordered_map<int, int> ng;
            stack<int> st;
            for (int i = n-1; i >= 0; --i) {
                while (!st.empty() && st.top() < nums[i]) st.pop();
                ng[nums[i]] = st.empty() ? -1 : st.top();
                st.push(nums[i]);
            }
            
            int m = findNums.size();
            vector<int> res(m);
            for (int i = 0; i < m; ++i) res[i] = ng[findNums[i]];
            return res;
        }
    };
    

    For Next Greater Element II:

    class Solution {
    public:
        vector<int> nextGreaterElements(vector<int>& nums) {
            if (nums.empty()) return {};
            int n = nums.size();
            vector<int> res(n, -1);
            stack<int> st;
            for (int i = 2*n-1; i >= 0; --i) {
                int num = nums[i%n];
                while (!st.empty() && nums[st.top()] <= num) st.pop();
                res[i%n] = st.empty() ? - 1 : nums[st.top()];
                st.push(i%n);
            }
            return res;
        }
    };
    

  • 0

    @yuxiangmusic

    Nice and clean.


  • 0
    A

    @yuxiangmusic Very elegant solution! Thank you!


  • 2
    C

    Brilliant solution!
    BTW, we can break if stack is empty:

    public class Solution {
        public int[] nextGreaterElements(int[] nums) {
            int n=nums.length, ans[]=new int[n];
            Arrays.fill(ans, -1);
            Stack<Integer> stack=new Stack<>();
            for (int i=0;i<2*n;i++) {
                while (!stack.isEmpty() && nums[stack.peek()]<nums[i%n]) ans[stack.pop()]=nums[i%n];
                if (i<n) stack.push(i);
                if (stack.isEmpty()) break; // break if stack is empty
            }
            return ans;
        }
    }
    

  • 0

    Here is my python version.
    The same as above, you can add break if you like.

    def nextGreaterElements(self, nums):
            stack, res = [], [-1] * len(nums)
            for i in range(len(nums)) * 2:
                while stack and (nums[stack[-1]] < nums[i]):
                    res[stack.pop()] = nums[i]
                stack.append(i)
            return res

  • 0
    F

    Thanks very much!
    It's very smart to use 2*n and i%n to deal with the rotational array.


  • 0
    C

    I did something similiar, not sure which one is a better complexity~ O(n) each on a higher level

    instead of traversing the array twice (push, pop etc) i am checking the max element in first iteration & later traversing n times around the max element

    https://discuss.leetcode.com/topic/83998/simple-solution-step-wise-2-iterations-of-array-o-n


  • 0
    F

    We can get rid of the stack by using the output array to do the work to reach O(1) extra space.
    Of course it comes with a cost that you need to transfer the index at the end, that results in 3 passes in total.
    Here is my solution:
    https://discuss.leetcode.com/topic/91617/simple-c-solution-o-n-time-o-1-extra-space-no-stack-using-output-array-only


  • 0
    Z

    @ckcz123 Actually the stack will not be empty, because the largest number is always in.


  • 0
    Z

    @vesion Why is backward faster? Is it test case dependent? I feel backward is equivalent to working forward on next smaller element.


  • 0
    X
    This post is deleted!

  • 5

    same idea, mine is from end

        public int[] nextGreaterElements(int[] nums) {
            int len = nums.length;
            int[] result = new int[len];
            Stack<Integer> stack = new Stack<>();
            for (int i = len * 2 - 1; i >= 0; i--) {
                while (!stack.isEmpty() && stack.peek() <= nums[i % len]) stack.pop();
                if (i < len) result[i] = stack.isEmpty()? -1 : stack.peek();
                stack.push(nums[i % len]);
            }
            return result;
        }
    

  • 0
    J

    @wuyangbu same is my mind


Log in to reply
 

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