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;
}
}
// 没想到用单调栈