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