现在是 2022 年了,你不知道什么是单调栈和单调队列吗? (下)

2022/9/11 6:23:22

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

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

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

介绍

阅读本文后,您将获得:

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

什么是单调栈

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

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

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

IMG_4320935EB9DD-1.jpeg

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

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

单调堆栈通常是解决 ** 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. 数字1 中的元素不一定存在于 数字2 在数组中。
  2. 我们通过 数字2 栈中的元素被压入单调栈(单调递减),当一个元素需要出栈时,我们可以知道 ** 即将入队的元素是即将被弹出的元素的第一个较大的值!**
  3. 完成第二步后,我们需要 数字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

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

image.png

给定 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个单位的雨(蓝色部分代表下雨)。

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

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

image.png

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

  1. 如果要压入堆栈的值等于堆栈顶部的值,我们该怎么办?直接入栈处理?还是弹出原始值并将新值压入堆栈? (其实可以)

  2. 我们在单调栈中存储的是索引值,而不是高度值,因为我们在计算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;  
 }  
 }  
 堆。推(一);  
 }  
 返回总和;  
 }  
  
 复制代码

image.png

接受!完毕!

概括

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

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

版权声明:本文为博主原创文章,遵循CC 4.0 BY-SA版权协议。转载请附上原文出处链接和本声明。

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

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明

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



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


扫一扫关注最新编程教程