十五周算法訓(xùn)練營——單調(diào)棧
今天是十五周算法訓(xùn)練營的第九周，主要講單調(diào)棧專題。（歡迎加入十五周算法訓(xùn)練營，與小伙伴一起卷算法）
每日溫度
給定一個整數(shù)數(shù)組 temperatures ，表示每天的溫度，返回一個數(shù)組 answer ，其中 answer[i] 是指對于第 i 天，下一個更高溫度出現(xiàn)在幾天后。如果氣溫在這之后都不會升高，請?jiān)谠撐恢糜?0 來代替。
示例 1:
輸入: temperatures = [73,74,75,71,69,72,76,73] 輸出: [1,1,4,2,1,1,0,0]
// 通過單點(diǎn)棧解決
// 單調(diào)棧主要解決下一個最大值問題
function dailyTemperatures(temperatures) {
const n = temperatures.length;
const result = (new Array(n)).fill(0);
const stack = [];
// 從后往前遍歷
for (let i = n - 1; i >= 0; i--) {
// 當(dāng)棧不為空且當(dāng)前值比棧頂內(nèi)容大時(shí)就進(jìn)行彈棧
while (stack.length > 0 && stack[stack.length - 1].val <= temperatures[i]) {
stack.pop();
}
// 如果棧內(nèi)有元素，則求解結(jié)果
if (stack.length > 0) {
result[i] = stack[stack.length - 1].index - i;
}
// 將當(dāng)前內(nè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 中數(shù)字 x 的 下一個更大元素 是指 x 在 nums2 中對應(yīng)位置 右側(cè) 的 第一個 比 x 大的元素。
給你兩個 沒有重復(fù)元素 的數(shù)組 nums1 和 nums2 ，下標(biāo)從 0 開始計(jì)數(shù)，其中nums1 是 nums2 的子集。
對于每個 0 <= i < nums1.length ，找出滿足 nums1[i] == nums2[j] 的下標(biāo) j ，并且在 nums2 確定 nums2[j] 的 下一個更大元素 。如果不存在下一個更大元素，那么本次查詢的答案是 -1 。
返回一個長度為 nums1.length 的數(shù)組 ans 作為答案，滿足 ans[i] 是如上所述的 下一個更大元素 。
示例 1：
輸入：nums1 = [4,1,2], nums2 = [1,3,4,2]. 輸出：[-1,3,-1] 解釋：nums1 中每個值的下一個更大元素如下所述：
- 4 ，用加粗斜體標(biāo)識，nums2 = [1,3,4,2]。不存在下一個更大元素，所以答案是 -1 。
- 1 ，用加粗斜體標(biāo)識，nums2 = [1,3,4,2]。下一個更大元素是 3 。
- 2 ，用加粗斜體標(biāo)識，nums2 = [1,3,4,2]。不存在下一個更大元素，所以答案是 -1 。
// 單調(diào)棧主要解決下一個最大值問題
function nextGreaterElement(nums1, nums2) {
// 首先根據(jù)單調(diào)棧得到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);
// 將當(dāng)前元素存入棧中
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));下一個更大元素
給定一個循環(huán)數(shù)組 nums （ nums[nums.length - 1] 的下一個元素是 nums[0] ），返回 nums 中每個元素的 下一個更大元素 。
數(shù)字 x 的 下一個更大的元素 是按數(shù)組遍歷順序，這個數(shù)字之后的第一個比它更大的數(shù)，這意味著你應(yīng)該循環(huán)地搜索它的下一個更大的數(shù)。如果不存在，則輸出 -1 。
示例 1:
輸入: nums = [1,2,1] 輸出: [2,-1,2] 解釋: 第一個 1 的下一個更大的數(shù)是 2； 數(shù)字 2 找不到下一個更大的數(shù)； 第二個 1 的下一個最大的數(shù)需要循環(huán)搜索，結(jié)果也是 2。
// 單調(diào)棧主要用于解決下一個最大值問題
// 因?yàn)闉檠h(huán)數(shù)組，為了解決該問題可以將數(shù)組翻倍
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();
}
// 將結(jié)果進(jìn)行存儲
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));
