单调栈结构(进阶)

[编程题]单调栈结构(进阶)

热度指数：15408 时间限制：C/C++ 2秒，其他语言4秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给定一个可能含有重复值的数组 arr，找到每一个 i 位置左边和右边离 i 位置最近且值比 arr[i] 小的位置。返回所有位置相应的信息。

输入描述:

第一行输入一个数字 n，表示数组 arr 的长度。
以下一行输入 n 个数字，表示数组的值

输出描述:

输出n行，每行两个数字 L 和 R，如果不存在，则值为 -1，下标从 0 开始。

示例1

输入

7
3 4 1 5 6 2 7

输出

备注:

算法知识视频讲解

Javascript

我摸的鱼比你吃的饭还多

贴个 js 版本，需要注意不要逐行输出，不然会一直超时

const rl = require("readline").createInterface({ input: process.stdin });
var iter = rl[Symbol.asyncIterator]();
const readline = async () => (await iter.next()).value;

void async function () {
    const n = await readline();
    const arr = (await readline()).split(' ').map((item) => Number(item));
    const stack = [];
    const res = new Array(n);

    for (let i = 0; i < n; i++) {
        const cur = arr[i];

        while (stack.length && arr[stack[stack.length - 1]] >= cur) {
            const top = stack.pop();
            res[top] = [stack.length ? stack[stack.length - 1] : -1, i];
        }

        stack.push(i);
    }

    while (stack.length) {
        const top = stack.pop();
        res[top] = [stack.length ? stack[stack.length - 1] : -1, -1];
    }

    for (let i = n - 1; i >= 0; i--) {
        const cur = arr[i];
        let right = res[i][1];

        if (right > 0 && arr[right] === cur) {
            right = res[right][1];
        }

        res[i][1] = right;
    }

    console.log(res.map((item) => item.join(' ')).join('\n'));
}()

发表于 2025-01-18 09:55:33 回复(0)