现在是 2022 年了，你不知道什么是单调栈和单调队列吗？（下）

2022/9/11 6:23:22

编程Tag： 元素队列堆栈 height 栈顶 2022 单调 nums2

本文主要是介绍现在是 2022 年了，你不知道什么是单调栈和单调队列吗？（下），对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

报名金石计划第一次挑战——分享10万奖池，这是我的第2篇文章，点击查看活动详情

从上面继续，现在是 2022 年了，你不知道什么是单调栈和单调队列吗？（上）——掘金（juejin.cn） .今天我们将讨论什么是单调堆栈。

介绍

阅读本文后，您将获得：

什么是单调栈
单调栈可以解决的问题
单调栈经典问题的解法

什么是单调栈

单调栈对应单调队列，只不过单调队列对应的出队方法是从队列头出列，而单调栈是从栈头弹出（单调队列对应的位置是在队列末尾出队）。他们遇到使他们不那么单调的元素的方式实际上是一致的。

让我们回顾一下当单调队列和单调堆栈入队/堆叠时如何处理元素：

对于单调递减的队列/堆栈：当一个元素准备好入队或推入堆栈时，它与 ** 栈尾/栈顶** 比较元素，如果该元素大于 ** 栈尾/栈顶** 如果很小，则进入队列并压入堆栈。详情请参考下图：

我们使用这个规则来保证队列和栈的单调性。所以单调队列和单调栈的入队和栈规则是一样的，只是它们的出队和栈符合队列和栈的特点，仅此而已。

单调堆栈解决了什么问题？

单调堆栈通常是解决 ** NGE（下一个大元素）问题** ，即对于一系列元素，找到比他大的下一个元素。

使用单调堆栈解决问题

496. 下一个更大的元素 I — LeetCode

nums1 中数字 x 的下一个较大元素是 nums2 中 x 对应位置右侧第一个大于 x 的元素。
给定两个数组 nums1 和 nums2，没有重复元素，下标从 0 开始，其中 nums1 是 nums2 的子集。
对于每个 0 <= i < nums1.length，找到下标 j 使得 nums1[i] == nums2[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。

首先想到的是蛮力解决方案。使用双循环可以很容易地解决这个问题，但是由于我们已经了解了单调堆栈，我们将使用单调堆栈来解决这个问题。

首先我们明确一点：

数字1 中的元素不一定存在于 数字2 在数组中。
我们通过 数字2 栈中的元素被压入单调栈（单调递减），当一个元素需要出栈时，我们可以知道 ** 即将入队的元素是即将被弹出的元素的第一个较大的值！**
完成第二步后，我们需要 数字1 查询即将弹出的元素是否存在。

有了上面的思路，我们可以写出如下代码：

 /** * @param { number[] } nums1 * @param { number[] } nums2 * @return { number[] } */  
 var nextGreaterElement = 函数（nums1，nums2）{  
 常量顶部 = ( s) => s[s.长度 - 1];  
  
 常量哈希 = {};  
 // 恢复哈希映射，按值查询索引。  
 for ( 让 i = 0; i < nums1.length; i++) {  
 哈希[nums1[i]] = i;  
 }  
 常量栈 = [nums2[0]];  
 const 结果 = 新数组（nums1.length）。填充（- 1）；  
 for ( 让 i = 1; i < nums2.length; i++) {  
 // 在单调栈的应用中，如果要压入栈的值大于栈顶的值，应该按照单调栈的规则弹出。  
 while (stack.length && nums2[i] > top(stack)) {  
 如果（哈希[顶部（堆栈）]！==无效0）{  
 结果[哈希[顶部（堆栈）]] = nums2[i];  
 }  
 堆。流行音乐（）;  
 }  
 堆。推（nums2[i]）；  
 }  
 返回结果；  
 };  
  
 复制代码

42. 赶雨——LeetCode

这个问题相当经典。是单调栈的经典应用问题。当然，除了使用单调栈，我们还可以使用双指针方案来解决问题。双指针的解决方案这里省略，主要说明使用单调栈的解决方案。

给定 n 表示每个宽度的非负整数 1 柱子的高度图，计算柱子下雨后能承受多少雨水。
输入：高度 = [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个单位的雨（蓝色部分代表下雨）。

如果我们使用单调堆栈，我们需要考虑是使用单调递增的单调堆栈还是单调递减的单调堆栈？显然，我们应该使用单调

因为当一个更大的元素即将被压入堆栈时，就会出现“坑”。

这里有几点需要特别注意：

如果要压入堆栈的值等于堆栈顶部的值，我们该怎么办？直接入栈处理？还是弹出原始值并将新值压入堆栈？（其实可以）
我们在单调栈中存储的是索引值，而不是高度值，因为我们在计算rain的面积时，是通过“宽×高”来计算的，我们需要知道左边的列之间的距离和正确距离的列。但是我们比较的时候，还是用高度值来比较的。

函数顶部（arr）{
返回 arr[arr.长度 - 1];
}
变量陷阱=函数（高度）{
让总和 = 0;
常量栈 = [ 0];
for ( 让 i = 1; i < 高度。长度; i++) {

if (height[i] < height[ top(stack)] {
// 要压入栈的元素小于栈顶元素，直接压入栈
堆。推（一）；
} else if (height[i] === height[ top(stack)]) {
// 待入栈的元素与栈顶元素相等，将原元素出栈，再将新元素入栈
堆。流行音乐（）;
堆。推（一）；
} 别的 {
while (stack.length && height[i] > height[ top(stack)]) {
// 待入栈的元素大于栈顶元素，不断向前递归，直到栈顶元素不小于新元素
// “pit”是栈顶的元素，
// 左列是栈顶元素下面的第一个元素
// 右列是要压入栈的元素
让中间=顶部（堆栈）；
堆。流行音乐（）;
如果（堆栈。长度）{
让 h = 数学。 min(height[ top(stack)], height[i]) - height[mid];
常量 w = i - 顶部（堆栈） - 1；
总和 += h * w;
}
}
堆。推（一）；
}
}
返回总和；
}
复制代码

上面的代码思路比较清晰，但是代码量好像比较大。我们可以做一些简化。其实我们发现，如果要压入栈的元素与栈顶元素相等，那么出栈再压回栈的操作其实是多余的。因此，我们可以进一步简化代码如下：

 函数顶部（arr）{  
 返回 arr[arr.长度 - 1];  
 }  
 变量陷阱=函数（高度）{  
 让总和 = 0;  
 常量栈 = [ 0];  
 for ( 让 i = 1; i < 高度。长度; i++) {  
 while (stack.length && height[i] > height[ top(stack)]) {  
 // 待入栈的元素大于栈顶元素，不断向前递归，直到栈顶元素不小于新元素  
 // “pit”是栈顶的元素，  
 // 左列是栈顶元素下面的第一个元素  
 // 右列是要压入栈的元素  
 让中间=顶部（堆栈）；  
 堆。流行音乐（）;  
 如果（堆栈。长度）{  
 让 h = 数学。 min(height[ top(stack)], height[i]) - height[mid];  
 常量 w = i - 顶部（堆栈） - 1；  
 总和 += h * w;  
 }  
 }  
 堆。推（一）；  
 }  
 返回总和；  
 }  
  
 复制代码

接受！完毕！

概括

今天学习的单调栈是常用的 ** NGE（下一个大元素）问题** 数据结构，除了经典的雨水，在 LeetCode 上使用单调栈还有很多问题。希望读者有空多多练习。

如果觉得这篇文章对你有用，别忘了给作者点个赞哦~

这篇文章的链接： https://homecpp.art/3710/7553/2250

本文链接：https://www.qanswer.top/25906/38021100

这篇关于现在是 2022 年了，你不知道什么是单调栈和单调队列吗？（下）的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！

现在是 2022 年了，你不知道什么是单调栈和单调队列吗？ （下）

介绍