Skip to main content

Template-MonotonicStack

link

// 输入一个数组 nums,请你返回一个等长的结果数组
// 结果数组中对应索引存储着下一个更大元素,如果没有更大的元素,就存 -1。

const nextGreaterElement = (nums: number[]): number[] => {
const ans: number[] = []

const monoStack: number[] = []

for (let i = nums.length - 1; i >= 0; i--) {
while (monoStack.length && monoStack[monoStack.length - 1] <= nums[i]) {
monoStack.pop()
}

ans[i] = monoStack.length ? monoStack[monoStack.length - 1] : -1
monoStack.push(nums[i])
}

return ans
}

console.log(
nextGreaterElement([2, 1, 2, 4, 3])
)

下标 link

// 输入一个数组 nums,请你返回一个等长的结果数组
// 结果数组中对应索引存储着下一个更大元素的 「下标」
// 如果没有更大的元素,就存 n。

const nextGreaterElement = (nums: number[]): number[] => {
const ans: number[] = []

const monoStack: number[] = []

for (let i = nums.length - 1; i >= 0; i--) {
while (monoStack.length && nums[monoStack[monoStack.length - 1]] <= nums[i]) {
monoStack.pop()
}

ans[i] = monoStack.length ? monoStack[monoStack.length - 1] : nums.length
monoStack.push(i)
}

return ans
}

参考来源