十五周算法训练营——单调栈

今天是十五周算法训练营的第九周，主要讲单调栈专题。（欢迎加入十五周算法训练营，与小伙伴一起卷算法）

每日温度

给定一个整数数组 temperatures ，表示每天的温度，返回一个数组 answer ，其中 answer[i] 是指对于第 i 天，下一个更高温度出现在几天后。如果气温在这之后都不会升高，请在该位置用 0 来代替。

示例 1:

输入: temperatures = [73,74,75,71,69,72,76,73] 输出: [1,1,4,2,1,1,0,0]

// 通过单点栈解决
// 单调栈主要解决下一个最大值问题
function dailyTemperatures(temperatures) {
    const n = temperatures.length;
    const result = (new Array(n)).fill(0);
    const stack = [];
    // 从后往前遍历
    for (let i = n - 1; i >= 0; i--) {
        // 当栈不为空且当前值比栈顶内容大时就进行弹栈
        while (stack.length > 0 && stack[stack.length - 1].val <= temperatures[i]) {
            stack.pop();
        }
        // 如果栈内有元素，则求解结果
        if (stack.length > 0) {
            result[i] = stack[stack.length - 1].index - i;
        }
        // 将当前内容存入栈中
        stack.push({
            val: temperatures[i],
            index: i
        });
    }

    return result;
}

const temperatures = [89,62,70,58,47,47,46,76,100,70];

console.log(dailyTemperatures(temperatures));

下一个更大元素I

nums1 中数字 x 的 下一个更大元素 是指 x 在 nums2 中对应位置 右侧 的 第一个 比 x 大的元素。

给你两个 没有重复元素 的数组 nums1 和 nums2 ，下标从 0 开始计数，其中nums1 是 nums2 的子集。

对于每个 0 <= i < nums1.length ，找出满足 nums1[i] == nums2[j] 的下标 j ，并且在 nums2 确定 nums2[j] 的 下一个更大元素 。如果不存在下一个更大元素，那么本次查询的答案是 -1 。

返回一个长度为 nums1.length 的数组 ans 作为答案，满足 ans[i] 是如上所述的 下一个更大元素 。

示例 1：

输入：nums1 = [4,1,2], nums2 = [1,3,4,2]. 输出：[-1,3,-1] 解释：nums1 中每个值的下一个更大元素如下所述：

• 4 ，用加粗斜体标识，nums2 = [1,3,4,2]。不存在下一个更大元素，所以答案是 -1 。
• 1 ，用加粗斜体标识，nums2 = [1,3,4,2]。下一个更大元素是 3 。
• 2 ，用加粗斜体标识，nums2 = [1,3,4,2]。不存在下一个更大元素，所以答案是 -1 。

// 单调栈主要解决下一个最大值问题
function nextGreaterElement(nums1, nums2) {
    // 首先根据单调栈得到nums2的下一个最大元素
    const map = new Map();
    const stack = [];

    for (let i = nums2.length - 1; i >= 0; i--) {
        // 将不合理的值弹出栈
        while (stack.length > 0 && nums2[i] > stack[stack.length - 1]) {
            stack.pop();
        }

        const nextGreaterVal = stack.length > 0 ? stack[stack.length - 1] : -1;
        map.set(nums2[i], nextGreaterVal);

        // 将当前元素存入栈中
        stack.push(nums2[i]);
    }

    const result = nums1.map(num => map.get(num));

    return result;
}

const nums1 = [4, 1, 2];
const nums2 = [1, 3, 4, 2];
console.log(nextGreaterElement(nums1, nums2));

下一个更大元素

给定一个循环数组 nums （ nums[nums.length – 1] 的下一个元素是 nums[0] ），返回 nums 中每个元素的 下一个更大元素 。

数字 x 的 下一个更大的元素 是按数组遍历顺序，这个数字之后的第一个比它更大的数，这意味着你应该循环地搜索它的下一个更大的数。如果不存在，则输出 -1 。

示例 1:

输入: nums = [1,2,1] 输出: [2,-1,2] 解释: 第一个 1 的下一个更大的数是 2； 数字 2 找不到下一个更大的数； 第二个 1 的下一个最大的数需要循环搜索，结果也是 2。

// 单调栈主要用于解决下一个最大值问题
// 因为为循环数组，为了解决该问题可以将数组翻倍
function nextGreaterElements(nums) {
    const result = [];
    const stack = [];

    const len = nums.length;
    for (let i = len * 2 - 1; i >= 0; i--) {
        // 判断栈顶元素是否符合要求
        while (stack.length > 0 && nums[i % len] >= stack[stack.length - 1]) {
            stack.pop();
        }

        // 将结果进行存储
        result[i % len] = stack.length > 0 ? stack[stack.length - 1] : -1;

        // 将其放入栈顶
        stack.push(nums[i % len]);
    }

    return result;
}

const nums = [1, 2, 1];
console.log(nextGreaterElements(nums));