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

作者：前端点线面 2023-05-29 07:31:35开发 前端 数字 x 的周算栈 下一个更大的元素 是按数组遍历顺序，这个数字之后的法训第一个比它更大的数，这意味着你应该循环地搜索它的练营下一个更大的数。如果不存在，单调则输出 -1 。周算栈

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

每日温度

给定一个整数数组 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));

责任编辑：武晓燕 来源： 前端点线面 单调栈数组循环

(责任编辑：探索)