[力扣] 算法 503 (C#)

503. 下一个更大元素 II

public class Solution {
    const int NON_EXIST = -1;
    public int[] NextGreaterElements(int[] nums)
    {
        if (nums?.Length == 0)
            return Array.Empty<int>();
        if (nums.Length == 1)
            return new int[] { NON_EXIST };
        var ret = new int[nums.Length];
        Array.Fill(ret, NON_EXIST);
        for (var i = ret.Length - 2; i >= 0; i--)
        {
            if (nums[i] < nums[i + 1])
            {
                ret[i] = i + 1;
            }
            else
            {
                var curr = i + 1;
                while (ret[curr] != NON_EXIST)
                {
                    curr = ret[curr];
                    if (nums[i] < nums[curr])
                    {
                        ret[i] = curr;
                        break;
                    }
                }
            }
        }
        for(var i = ret.Length - 1; i >= 0; i--)
        {
            if (ret[i] != NON_EXIST)
                continue;
            var next = (i + 1) % ret.Length;
            while (next != NON_EXIST)
            {
                if(nums[i] < nums[next])
                {
                    ret[i] = next;
                    break;
                }
                next = ret[next];
            }
        }
        for (var i = 0; i < ret.Length; i++)
            if (ret[i] != NON_EXIST)
                ret[i] = nums[ret[i]];
        return ret;
    }
}

// 没想到用单调栈

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注