2 solutions, with and without stack


  • 0

    The without stack solution actually runs faster!

    Without Stack:

        public int[] NextGreaterElement(int[] findNums, int[] nums)
        {
            int[] result = new int[findNums.Length];
            Dictionary<int, int> Indices = new Dictionary<int, int>();
    
            for (int i = 0; i < nums.Length; i++)
            {
                Indices.Add(nums[i], i);
            }
    
            for (int i = 0; i < findNums.Length; i++)
            {
                result[i] = FindNextGreater(Indices[findNums[i]], findNums[i], nums);
            }
    
            return result;
        }
        private int FindNextGreater(int index, int num, int[] nums)
        {
            for (int i = index; i < nums.Length; i++)
            {
                if (nums[i] > num)
                    return nums[i];
            }
            return -1;
        }
    

    With Stack:

        public int[] NextGreaterElement(int[] findNums, int[] nums)
        {
            Stack<int> stack = new Stack<int>();
            Dictionary<int, int> indices = new Dictionary<int, int>();
    
            for (int i = 0; i < nums.Length; i++)
            {
                while (stack.Any() && stack.Peek() < nums[i])
                {
                    indices.Add(stack.Pop(), nums[i]);
                }
                stack.Push(nums[i]);
            }
    
            for (int i = 0; i < findNums.Length; i++)
            {
                findNums[i] = (indices.ContainsKey(findNums[i])) ? indices[findNums[i]] : -1;
            }
            return findNums;
        }
    

Log in to reply
 

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