栈

function isValid(s: string): boolean {
    let set = new Set(['()', '[]', '{}'])
    let stack = []
    for (let v of s) {
        if (set.has(stack.at(-1) + v)) {
            stack.pop()
        } else {
            stack.push(v)
        }
    }
    return stack.length === 0
};

function dailyTemperatures(temperatures: number[]): number[] {
    let res = Array(temperatures.length).fill(0)
    let stack = []
    for (let [k, v] of temperatures.entries()) {
        while (stack.length > 0 && v > temperatures[stack.at(-1)]) {
            let i = stack.pop()
            res[i] = k - i
        }
        stack.push(k)
    }
    return res
};

function nextGreaterElement(nums1: number[], nums2: number[]): number[] {
    let map = new Map()
    let stack = []
    for (let [i, v] of nums2.entries()) {
        while (stack.length > 0 && nums2[stack.at(-1)] < v) {
            map.set(nums2[stack.pop()], v)
        }
        stack.push(i)
    }
    return nums1.map(x => map.get(x) ?? -1)
};

function nextGreaterElements(nums: number[]): number[] {
    let len = nums.length
    let res = Array(len).fill(-1)
    let stack = []
    let arr = [...nums, ...nums]
 
    for (let [i, v] of arr.entries()) {
        while (stack.length > 0 && arr[stack.at(-1)] < v) {
            console.log(stack.at(-1), v)
            res[stack.pop()] = v
        }
        if (i < len) stack.push(i)
    }
    return res
};

function calculate(s: string): number {
    let tokens = s.replace(/ /g, '').split(/(\D)/g)
    let nums = []
    let op = '+'
    for (let t of tokens) {
        if (/\D/.test(t)) {
            op = t
        } else {
            if (op === '+') nums.push(Number(t))
            else if (op === '-') nums.push(-Number(t))
            else if (op === '*') nums.push(Number(nums.pop()) * Number(t))
            else if (op === '/') nums.push(parseInt(String(Number(nums.pop()) / Number(t))))
        }
    }
    return nums.reduce((a, b) => a + b)
};

function evalRPN(tokens: string[]): number {
    let stack = []
    for (let t of tokens) {
        if (/\d/.test(t)) {
            stack.push(Number(t))
        } else {
            console.log(stack)
            let [l, r] = stack.splice(-2)
            if (t === '+') stack.push(l + r)
            else if (t === '-') stack.push(l - r)
            else if (t === '*') stack.push(l * r)
            else if (t === '/') stack.push(parseInt(String(l / r)))
        }
    }
    return stack[0]
};

function decodeString(s: string): string {
    let tokens = s.split(/(\d+|\W)/).filter(x => x !== '')
    let stack = []
    for (let t of tokens) {
        if (t !== ']') {
            stack.push(t)
        } else {
            let i = stack.lastIndexOf('[')
            let str = stack.splice(i + 1).join('')
            stack.pop()
            let num = Number(stack.pop())
            stack.push(str.repeat(num))
        }
    }
    return stack.join('')
};

function validateStackSequences(pushed: number[], popped: number[]): boolean {
    let index = 0
    let stack = []
    for (let v of pushed) {
        stack.push(v)
        while (stack.length && stack.at(-1) === popped[index]) {
            stack.pop()
            index++
        }
    }
    return index === popped.length
};