十五周算法訓練營——單調棧
今天是十五周算法訓練營的第九周，主要講單調棧專題。（歡迎加入十五周算法訓練營，與小伙伴一起卷算法）
每日溫度
給定一個整數數組 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));
