单调栈模板：下一个更大元素/每日温度/移掉K位数字/接雨水
Author：zhoulujun Date：
关于数据结构的部分
《再谈js数据类型与对象数据结构底层实现原理-object array map set》
《算法与数据结构面试通关经验总结：leetCode刷题经验》
因为底部被封住了，所以只能先进后出
单调栈
单调栈是一种特殊的数据结构，其特点是栈内的元素按照一定的单调性排列，可以是单调递增或单调递减。就和数组排列是顺序或者逆序是一个道理。
单调栈用途不太广泛，只处理一类典型的问题，比如「下一个更大元素」，「上一个更小元素」等。本文用讲解单调队列的算法模版解决「下一个更大元素」开始讲解相关的问题。
单调栈思想模板：
维护一个递增或者递减的stack，找出stack具体存什么(下标或者项数值)，单调数据存入栈中，遇到非单调数据就出栈，以及其他的一些计算操作,并且直到栈种的数据重新回归单调。更新栈后继续遍历。
和当前的栈顶比较，如果符合条件了就会被弹出，后面的数就会成为栈顶，所以整个栈里的每个元素早晚都会成为栈顶，只用跟栈顶比较就行
function monotoneStack(数据参数){
const stack = []
定义一个结果容器
for(遍历数据){
while(stack.length && 满足一个判断条件){
出栈操作
其他的一些计算
}
入栈操作
}
返回结果
}如果找的是第一个更大的元素，那么只要遇到比栈顶元素大的元素，就弹出栈顶元素，因此留在栈里的只能是从栈头到栈底的递增顺序。同理，
如果找的是第一个更小的元素，那么只要遇到比栈顶元素更小的元素，就弹出栈顶元素，因此留在栈里的是从栈头到栈底的递减顺序。
单调栈用来解决的问题
单调栈能实现：左边最后一个最小或者最大，右边第一个最小或者最大，这四种查询场景
单调栈来排序
具体演示可以观看：https://www.bilibili.com/video/BV1bb4y1T7sL
排序过程：
遍历数组 arr 中的每一个元素：
如果栈顶元素小于等于当前元素，将当前元素压入 stack。
如果栈顶元素大于当前元素，则将栈顶元素依次弹出并压入 tempStack，直到栈顶元素小于等于当前元素为止，然后将当前元素压入 stack。
如果 stack 是空的，直接将当前元素压入 stack。
如果 stack 不为空，则比较栈顶元素与当前元素的大小：
将 tempStack 中的元素依次弹出并压入 stack，完成一轮遍历后，stack 中的元素即为按非递减顺序排列的数组。
function sortArrayWithStack(arr) {
let stack = [];
let tempStack = [];
for (let i = 0; i < arr.length; i++) {
let current = arr[i];
// 如果 stack 是空的，直接将当前元素压入 stack。如果 stack 不为空，则比较栈顶元素与当前元素的大小：
while (stack.length > 0 && stack[stack.length - 1] > current) {
tempStack.push(stack.pop());
}
stack.push(current);
while (tempStack.length > 0) {
stack.push(tempStack.pop());
}
}
return stack;
}时间复杂度：在最坏情况下，每个元素都可能需要从 stack 中弹出和压入 tempStack，导致内部循环的执行次数为 O(n)。因此，总体时间复杂度为
O(n^2)
空间复杂度：算法使用了两个辅助栈 stack 和 tempStack，它们的空间复杂度与输入数组大小 n 成正比，因此空间复杂度为 O(n)。
与常见的排序算法（如快速排序、归并排序、堆排序等）相比，该算法的时间复杂度较高。然而，对于特定问题，特别是需要栈操作或者已知数据分布的情况下，这种简单的栈排序算法可以提供一种解决方案。
单调栈的问题
下一个更大元素合集
下一个更大元素 II
给定一个循环数组 nums （ nums[nums.length - 1] 的下一个元素是 nums[0] ），返回 nums 中每个元素的 下一个更大元素 。
数字 x 的 下一个更大的元素 是按数组遍历顺序，这个数字之后的第一个比它更大的数，这意味着你应该循环地搜索它的下一个更大的数。如果不存在，则输出 -1 。
示例 1: 输入: nums = [1,2,1] 输出: [2,-1,2]
解释: 第一个 1 的下一个更大的数是 2； 数字 2 找不到下一个更大的数； 第二个 1 的下一个最大的数需要循环搜索，结果也是 2。
首先是为什么要用单调栈？因为这道题要找到每个元素之后的首个大于它的元素，可以通过维护一个从栈底到栈顶单调递减的栈实现。
暴力解法中，如果数组的前半部分是单调不增的，那么会有很大的计算资源的浪费。比如说 [6,5,4,3,8]，对于前面的 [6,5,4,3] 等数字都需要向后遍历，当寻找到元素 8 时才找到了比自己大的元素；而如果已知元素 6 向后找到元素 8 才找到了比自己的大的数字，那么对于元素 [5,4,3] 来说，它们都比元素 6 更小，所以比它们更大的元素一定是元素 8，不需要单独遍历对 [5,4,3] 向后遍历一次！
根据上面的分析可知，可以遍历一次数组，如果元素是单调递减的（则他们的「下一个更大元素」相同），我们就把这些元素保存，直到找到一个较大的元素；把该较大元素逐一跟保存了的元素比较，如果该元素更大，那么它就是前面元素的「下一个更大元素」。
在实现上，我们可以使用「单调栈」来实现，单调栈是说栈里面的元素从栈底到栈顶是单调递增或者单调递减的（类似于汉诺塔）。
既然方法选好了，那就套用模板来解决。
分析可知，遇到大数就记录，并且会产生一个数组，因此可以用下标的来记录单调递减的栈。一个技巧在于，数组顶多循环两次，因此可以直接将数组本身复制之后拼接到数组后面。遍历新数组,去结果数组的一半。
var nextGreaterElements = function (nums) {
const len = nums.length, result = new Array(len * 2).fill(-1), stack = [];
nums = nums.concat(nums);
for (let i = 0; i < len * 2; i++) {
while (stack.length && nums[i] > nums[stack[stack.length - 1]]) {
const num = stack.pop();
result[num] = nums[i];
}
stack.push(i);
}
return result.slice(0, len);
};对此做一个简单的变形
下一个更大元素 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]
解释:
对于 num1 中的数字 4 ，你无法在第二个数组中找到下一个更大的数字，因此输出 -1 。
对于 num1 中的数字 1 ，第二个数组中数字1右边的下一个较大数字是 3 。
对于 num1 中的数字 2 ，第二个数组中没有下一个更大的数字，因此输出 -1 。
示例 1： 输入：nums1 = [2,4], nums2 = [1,2,3,4]. 输出：[3,-1]
如果我们直接使用暴力，即双遍历：针对每一个 nums1 中的元素，我们先找到它在 nums2 中的位置，再从那个位置往右找到第一个比它大的数即可。
function nextGreaterElement(const[] nums1, const[] nums2) {
const n = nums1.length,m = nums2.length,ans = new Array(n);
for (let i = 0; i < n; i++) {
// 先找到nums1[i]在nums2中的位置
let j = 0;
while (j < m && nums2[j] != nums1[i]) {
j++;
}
// 再往右找到第一个比它大的数
while (j < m && nums2[j] <= nums1[i]) {
j++;
}
// 构造答案
if (j >= m) {
ans[i] = -1;
} else {
ans[i] = nums2[j];
}
}
return ans;
}上面的代码，每个 nums1 中的元素我们都要在 nums2 中从头开始遍历，这个效率是非常低的，那么，我们有没有什么方法降低遍历的次数呢？
我们可以先用哈希表记录 nums1 中的所有元素及其位置，直接遍历 nums2，然后看 nums2 中的每一个元素是否在哈希表中，在的话，我们才往右寻找比它大的数，这样可以极大地减少遍历的次数。
function nextGreaterElement(nums1, nums2) {
const n = nums1.length, m = nums2.length, map = new Map();
for (let i = 0; i < n; i++) {
map.set(nums1[i], i);
}
const ans = new Array(n);
for (let i = 0; i < m; i++) {
if (map.has(nums2[i])) {
// 对于在nums1中的元素，才向右查找
let j = i + 1;
while (j < m && nums2[j] <= nums2[i]) {
j++;
}
ans[map.get(nums2[i])] = j >= m ? -1 : nums2[j];
}
}
return ans;
}方法二中对于每一个在 nums1 中的元素，我们还是需要往右遍历 nums2 才能找到第一个比它大的数，这个效率也是有点低下的，有没有方法改进呢？
这就是本题的主要解题思路，单调栈。
首先我们应该注意到nums1是nums2的子集，因此，我们可以首先忽略nums1，而是对 nums2 中的每一个元素，求出其下一个更大的元素。随后对于将这些答案放入哈希映射（HashMap）中，再遍历数组 nums1，利用哈希表的查找优势直接找出答案——
使查询 nums 1中的每个元素在 nums 2中对应位置的右边的第一个更大的元素值时不需要再遍历 nums 。
而如何查找nums2中的下一个更大元素，这里主要的思想是单调栈，首先把第一个元素 nums2[1] 放入栈，随后对于第二个元素 nums2[2]，如果 nums2[2] > nums2[1]，那么我们就找到了 nums2[1] 的下一个更大元素 nums2[2]，此时就可以把 nums2[1] 出栈并把 nums2[2] 入栈；如果 nums2[2] <= nums2[1]，我们就仅把 nums2[2] 入栈。对于第三个元素 nums2[3]，此时栈中有若干个元素，那么所有比 nums2[3] 小的元素都找到了下一个更大元素（即 nums2[3]），因此可以出栈，在这之后，我们将 nums2[3] 入栈，以此类推。
相当于我们维护了一个单调不增（从栈顶到栈顶）的栈，换言之，每次考察一个元素，而栈中的数如果比其小，那么该元素就是这些数对应的下一个元素，因此保持单调性即可找到所有要求的值。
总结，就是将题目分解为两个子问题：
第 1 个子问题：如何更高效地计算 nums2 中每个元素右边的第一个更大的值（单调栈）；
第 2 个子问题：如何存储第 1 个子问题的结果（哈希表）。
var nextGreaterElement = function (nums1, nums2) {
const map = new Map(), stack = [];
for (let i = nums2.length - 1; i >= 0; --i) {
const num = nums2[i];
while (stack.length && num >= stack[stack.length - 1]) {
stack.pop();
}
map.set(num, stack.length ? stack[stack.length - 1] : -1);
stack.push(num);
}
const res = new Array(nums1.length).fill(0).map((_, i) => map.get(nums1[i]));
return res;
};下一个更大元素 III
这一题其实跟单调栈没有啥关系，但是还是把他讲了
给你一个正整数 n ，请你找出符合条件的最小整数，其由重新排列 n 中存在的每位数字组成，并且其值大于 n 。如果不存在这样的正整数，则返回 -1 。
示例 1： 输入：n = 12 输出：21
示例 2： 输入： n = 21 输出：-1
题目是让我们重新排列数字，找到大于 n 的最小整数，和「下一个排列」很像，题目详情可见 下一个排列
算法推导
https://leetcode.cn/problems/next-greater-element-iii/solutions/1642334/by-lfool-vi69/
如何得到这样的排列顺序？这是本文的重点。我们可以这样来分析：
我们希望下一个数比当前数大，这样才满足「下一个排列」的定义。因此只需要将后面的「大数」与前面的「小数」交换，就能得到一个更大的数。比如 123，将 2 和 3 交换就能得到一个更大的 132
我们还希望下一个数增加的幅度尽可能的小，这样才满足「下一个排列与当前排列紧邻」的要求。为了满足这个要求，我们需要：
在尽可能靠右的低位进行交换，需要从后向前查找
将一个尽可能小的「大数」与前面的「小数」交换。比如 123465 ，下一个排列应该把 5 和 4 交换而不是把 6 和 4 交换
将「大数」换到前面后，需要将「大数」后面的所有数重置为升序，升序排列就是最小的排列。以 123465 为例：首先按照上一步，交换 5 和 4，得到 123564；然后需要将 5 之后的数重置为升序，得到 123546。显然 123546 比 123564 更小，123546 就是 123465 的下一个排列
算法过程
标准的 “下一个排列” 算法可以描述为：
从后向前 查找第一个 相邻升序 的元素对 (i,j)，满足 A[i] < A[j]。此时 [j,end) 必然是降序
这里 i=4，j=5，对应的值为 5，7
在 [j,end) 从后向前 查找第一个满足 A[i] < A[k] 的 k。A[i]、A[k] 分别就是上文所说的「小数」、「大数」
这里 A[i] 是 5，故 A[k] 是 6
将 A[i] 与 A[k] 交换
可以断定这时 [j,end) 必然是降序，逆置 [j,end)，使其升序
如果在步骤 1 找不到符合的相邻元素对，说明当前 [begin,end) 为一个降序顺序，则直接跳到步骤 4
橙色是蓝色的下一个排列
最终代码
function nextPermutation(nums) {
const n = nums.length;
let j = -1; // Step 1: Find the largest index k such that nums[k] < nums[k + 1]
for (let i = n - 2; i >= 0; i--) { // 从后向前查找第一个相邻升序的元素对
if (nums[i] < nums[i + 1]) {
j = i;
break;
}
}
if (j === -1) { // 找不到符合的相邻元素对，说明当前 [begin,end) 为一个降序顺序, reverse nums and return
nums.reverse();
return;
}
let k = -1;// Step 2: Find the largest index k greater than j such that nums[j] < nums[k]
for (let i = n - 1; i > j; i--) {
if (nums[i] > nums[j]) {
k = i;
break;
}
}
[nums[j], nums[k]] = [nums[k], nums[j]];// Step 3: Swap nums[j] and nums[k]
let left = j + 1, right = n - 1;// Step 4: Reverse the sequence from nums[j + 1] to the end
while (left < right) {
[nums[left], nums[right]] = [nums[right], nums[left]];
left++;
right--;
}
}移掉 K 位数字
给你一个以字符串表示的非负整数 num 和一个整数 k ，移除这个数中的 k 位数字，使得剩下的数字最小。请你以字符串形式返回这个最小的数字。
示例 1 ：输入：num = "1432219", k = 3 输出："1219" 解释：移除掉三个数字 4, 3, 和 2 形成一个新的最小的数字 1219 。
示例 2 ：输入：num = "10200", k = 1 输出："200" 解释：移掉首位的 1 剩下的数字为 200. 注意输出不能有任何前导零。
示例 3 ：输入：num = "10", k = 2 输出："0" 解释：从原数字移除所有的数字，剩余为空就是 0 。
对于两个相同长度的数字序列，最左边不同的数字决定了这两个数字的大小，例如，对于 A=1axxx，B=1bxxx，如果 a>b 则 A>B。
基于此，我们可以知道，若要使得剩下的数字最小，需要保证靠前的数字尽可能小。
例如 425，如果要求我们只删除一个数字，那么从左到右，我们有 4、2 和 5 三个选择。我们将每一个数字和它的左邻居进行比较。从 2 开始，2 小于它的左邻居 4。假设我们保留数字 4，那么所有可能的组合都是以数字 4（即 42，45）开头的。相反，如果移掉 4，留下 2，我们得到的是以 2 开头的组合（即 25），这明显小于任何留下数字 4 的组合。因此我们应该移掉数字 4。如果不移掉数字 4，则之后无论移掉什么数字，都不会得到最小数。
这样来看, 我们实际上是在找某个元素右边第一个比他小的元素（单调栈：严格单调递增）, 以代替该元素, 那自然就是单调栈了.
单调栈
从左到右遍历字符串，如果栈非空&&栈顶元素>=当前字符&&k!=0，则弹栈，并最后将当前字符入栈。
基于上述分析，我们可以得出「删除一个数字」的贪心策略：给定一个长度为 n 的数字序列 [D0D1D2D3…Dn]，从左往右找到第一个位置 i（i>0）使得 Di<Di−1，并删去 D i−1；如果不存在，说明整个数字序列单调不降，删去最后一个数字即可。
基于此，我们可以每次对整个数字序列执行一次这个策略；删去一个字符后，剩下的 n−1 长度的数字序列就形成了新的子问题，可以继续使用同样的策略，直至删除 k 次。
var removeKdigits = function (num, k) {
const remainCount = num.length - k, stack = [];
for (const digit of num) {
while (k > 0 && stack.length !== 0 && +stack[stack.length - 1] > +digit) {
stack.pop();
k--;
}
stack.push(digit);
}
return stack.slice(0, remainCount).join('').replace(/^0+/, '') || '0';
};每日温度（Daily Temperatures）
给定一个整数数组 temperatures ，表示每天的温度，返回一个数组 answer ，其中 answer[i] 是指对于第 i 天，下一个更高温度出现在几天后。如果气温在这之后都不会升高，请在该位置用 0 来代替。
示例 1: 输入: temperatures = [73,74,75,71,69,72,76,73] 输出: [1,1,4,2,1,1,0,0]
示例 2: 输入: temperatures = [30,40,50,60] 输出: [1,1,1,0]
这个题目使用暴力法时，当数据量很大的时候，两层for循环——时间复杂度O(n2)，将会耗费巨大的性能损耗。
假如用单调栈维护一个项数递减的下标，遇到大于栈顶的项，就开始pop，并记录下下标之间对应的差值，就是所求的值。
var dailyTemperatures = function(temperatures) {
if(temperatures.length == 1)return [0]
// 定义一个长度为气温列表长度的结果数组res，栈的值就是第一个最大元素的下标（注意一定是下标）。定义一个空栈stack。
const result = new Array(temperatures.length).fill(0), stack = [0];
for(let i = 1 ; i < temperatures.length ; i++){ // 开始for循环。然后当前元素与栈顶元素，不断出入栈。
while(stack.length && temperatures[i] > temperatures[stack[stack.length - 1]]){
let idx = stack.pop()
result[idx] = i - idx//两下标相减记录下距离
}
stack.push(i)
}
return result
};接雨水
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
示例1：输入：height = [0,1,0,2,1,0,1,3,2,1,2,1] 输出：6
解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。
在《对撞双指针专题：接雨水系列问题 》用对撞来解决（双指针法相对更简单直观，适合于快速实现和理解），哪为什么要使用单调栈？
单调栈在处理一些复杂的高度分布情况时表现更佳——能够处理所有情况，时间复杂度稳定！
按照思想来走一遍，维护一个stack，单调递减存储数组的项数，如果遇到增项则可能会产生接雨水区域。
接雨水代码
var trap = function (height) {
let result = 0;
const stack = [0];
if (height.length <= 2) return 0;
for (let i = 1; i < height.length; i++) {
while (stack.length && height[i] > height[stack[stack.length - 1]]) {
let top = stack.pop();
if (!stack.length) break;
let left = stack[stack.length - 1];
let trapHeight = Math.min(height[left], height[i]) - height[top];
let trapWidth = i - left - 1;
result += trapHeight * trapWidth;
}
stack.push(i);
}
return result;
};参考文章：
【LeetCode】下一个更大元素（I、II、III） https://www.cnblogs.com/gzshan/p/12548893.html
力扣402题移掉k位数字 https://blog.csdn.net/weixin_45863060/article/details/122814849
用javascript分类刷leetcode13.单调栈(图文视频讲解) https://cloud.tencent.com/developer/article/2205708
深入浅出搞通单调队列单调栈 https://www.eet-china.com/mp/a38370.html
Leetcode接雨水系列问题 https://blog.csdn.net/qq_39144436/article/details/124315096
转载本站文章《单调栈模板：下一个更大元素/每日温度/移掉K位数字/接雨水》,
请注明出处：https://www.zhoulujun.cn/html/theory/algorithm/leetcode/9069.html