程序员经验分享-hwhale

12.单调栈——解决接雨水和柱状图中的最大矩形等问题

2023-05-16

单调栈

1.单调栈实现结构

单调栈解决的问题：给你一个数组,想要用尽可能低的代价知道数组中每一个元素的左边元素比它大的或者右边元素比他大的信息是什么。如果用暴力方法，左边遍历一次右边遍历一次，时间复杂度为O(N^2),用单调栈的方法可以使得时间复杂度变成O(N)。

【例】求数组[5 4 6 7]每个元素左、右两边比他大最近的元素下标。

5左边比他大的无、右边比它大的元素6对应的2；

4左边比它大的5对应的下标0、右边比它大的元素6对应的下标2；

6左边比它大的无、右边比它大的元素7对应的下标3；

7左边比它大的无、右边比它大的无。

1.1单调栈实现过程

以求数组中每个元素左右最近的比它大的元素下标为例（小的同理），**栈从栈底到栈顶要保持单调递减。**过程如下：

  1. 依次遍历数组元素，栈顶元素下标对应的数大于当前的元素，则将当前元素的下标放入栈中。
  2. 如果栈顶元素下标对应的数小于当前的元素，则弹出栈顶元素，记录栈顶元素下标的左边比它大的元素下标为弹出后的栈顶元素或者无，右边比它大的元素的下标为当前元素的下标。循环往复，直到栈顶元素对应的数大于当前元素，将当前元素的下标放入栈中。
  3. 当遍历完数组后，进入清算阶段，栈中还剩下的元素依次弹出，并如步骤2记录每个弹出的元素的左右比它大的元素的下标。

【例】数组[5 4 3 6 1 2 0],用单调栈找到数组中每一个元素，左右离它最近的元素的下标。

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-3sGqiDdT-1651157640721)(C:\Users\ThinkStation K\AppData\Roaming\Typora\typora-user-images\1650963460538.png)]

过程如下：

1.下标0、1、2元素入栈，由于遵循单调栈的单调性，直接插入栈中。

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-EQSNx93E-1651157640722)(C:\Users\ThinkStation K\AppData\Roaming\Typora\typora-user-images\1650963510910.png)]

2.轮到3下标对应元素6准备入栈，但栈顶元素2下标对应元素3小于6，2下标对应元素3出栈。此时，记录下标2元素左边比它大的元素下标为1，右边比它大的元素下标为3.

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-M4ItNKHe-1651157640722)(C:\Users\ThinkStation K\AppData\Roaming\Typora\typora-user-images\1650963733514.png)]

3.轮到3下标对应元素6准备入栈，但栈顶元素1下标对应元素4小于6，1下标对应元素4出栈。此时，记录下标1元素左边比它大的元素下标为1，右边比它大的元素下标为3.

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-ze4Urb4O-1651157640723)(C:\Users\ThinkStation K\AppData\Roaming\Typora\typora-user-images\1650963793848.png)]

4.轮到3下标对应元素6准备入栈，但栈顶元素0下标对应元素5小于6，0下标对应元素5出栈。此时，记录下标0元素左边比它大的元素下标为无，右边比它大的元素下标为3.

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-LWkuvRLD-1651157640723)(C:\Users\ThinkStation K\AppData\Roaming\Typora\typora-user-images\1650963851316.png)]

5.下标4元素遵从单调栈的单调性，入栈。

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-pJTMdETX-1651157640723)(C:\Users\ThinkStation K\AppData\Roaming\Typora\typora-user-images\1650963864254.png)]

6.轮到5下标对应元素2准备入栈，但栈顶元素4下标对应元素1小于2，4下标对应元素1出栈。此时，记录下标4元素左边比它大的元素下标为3，右边比它大的元素下标为5.

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-fyKpLkKA-1651157640724)(C:\Users\ThinkStation K\AppData\Roaming\Typora\typora-user-images\1650963913837.png)]

7.下标6元素遵从单调栈的单调性，入栈。

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-QGEOdfSA-1651157640724)(C:\Users\ThinkStation K\AppData\Roaming\Typora\typora-user-images\1650965400097.png)]

8.数组遍历结束，进入清算阶段，栈中元素依次弹出，记录每个弹出元素的左右下标。

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-0XWLAV9M-1651157640724)(C:\Users\ThinkStation K\AppData\Roaming\Typora\typora-user-images\1650965445973.png)]

1.2代码

1.数组中有重复值的情况。

思路：考虑在上述过程的基础上，将放入栈中的下标换成链表即可，如果栈顶下标元素和数组遍历到的数相同，就将相同的下标压到链表中。

map<int, pair<int, int>> getRes(vector<int>& nums) {
    map<int, pair<int, int>> res; //存放每个元素左右离它最近的元素的下标
    stack<list<int>> st;
    //进入遍历阶段
    for (int i = 0; i < nums.size(); ++i) {
        if (st.empty() || nums[i] < nums[st.top().back()]) {
            st.push(list<int>{i});
        } else if (nums[i] == nums[st.top().back()]) {
            st.top().push_back(i);
        } else {
            while (!st.empty() && nums[i] > nums[st.top().back()]) {
                list<int> tmp = st.top();
                st.pop();
                for (int k : tmp) {
                    int left = st.empty() ? -1 : st.top().back();
                    res[k] = {left, i};
                }
            }
            if (st.empty() || nums[st.top().back()] != nums[i]) {
                st.push(list<int>{i});
            } else {
                st.top().push_back(i);
            }
        }
    }
    //进入清算阶段
    while (!st.empty()) {
        list<int> tmp = st.top();
        st.pop();
        for (int k : tmp) {
            int left = st.empty() ? -1 : st.top().back();
            res[k] = {left, -1};
        }
    }
    return res;
}

2.数组中无重复值的情况

//待放入单调栈的数组
map<int, pair<int, int>> getRes(vector<int>& nums) {
    map<int, pair<int, int>> res; //存放每个元素左右离它最近的元素的下标
    stack<int> st;
    
    //进入遍历阶段
    for (int i = 0; i < nums.size(); ++i) {
        if (nums[st.top()] > nums[i]) {
            st.push(i);
            continue;
        }
        while (!st.empty() && nums[st.top()] < nums[i]) {
            int tmp = st.top();
            st.pop();
            int left = st.empty() ? -1 : st.top();
            res[tmp] = { left, i };
        }
        st.push(i);
    }
    //进入清算阶段
    while (!st.empty()) {
        int tmp = st.top();
        st.pop();
        int left = st.empty() ? -1 : st.top();
        res[tmp] = { left, -1 };
    }
    return res;
}

2.例题

单调栈中问题可以根据题目的不同进行简化，但主要思想是通过求解每个位置左右比它大（小）位置的信息来求解问题。可能只需要用到左边信息，可能只用到右边信息，解题时可以随着题目的不同来简略上述代码。

【例1】接雨水

力扣题目链接(opens new window)

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

示例 1：

img

  • 输入：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 个单位的雨水（蓝色部分表示雨水）。

【思路】

可以是单调栈的经典题目。思路如下：

  1. 可以看出只有左右都存在比当前位置都高的柱子才能够放得下雨水。即需要知道每个位置元素的比它左右都大的元素下标。
  2. 那么所有的雨水该怎么计算？由于木桶效应，能存放的水由最短的那根木桶决定，这题也是一样，如果一个位置左右都存在最大值，那么能存放的雨水由左右比它大的最低的那根柱子决定。 即第i个位置左右比它高的柱子下标为left和right，存放的雨水为(right - left - 1) × min(height[left], height[right]).
  3. 但如果存在连续的左右更大值的位置，如事例中第4、5、6位置，用这个方法会重复算了一部分面积，这主要是因为连续位置中存在两个位置的下标的高度相同，导致重复算了这部分的雨水面积。那我们对连续位置中存在相同位置的下标只算一次就行。
  4. 回到代码部分，由于清算部分一定不存在右边比它大的位置，所以这部分肯定不能存放雨水可以忽略掉。
  5. 只有遍历部分存在左右都有比它高的位置，我们就找出这部分位置，求出这些位置所对应的雨水。
  6. 而对于连续位置中存在不同位置下标高度相等的柱子，由于栈中存放的是下标的链表，如果出现上述情况，这些不同位置的下标会被放在同一个链表中，那么我们只要对链表中的高度计算一次雨水面积就可以。
class Solution {
public:
    int trap(vector<int>& nums) {
        int res = 0; //存放每个元素左右离它最近的元素的下标
        stack<list<int>> st;
        //遍历阶段
        for (int i = 0; i < nums.size(); ++i) {
            if (st.empty() || nums[i] < nums[st.top().back()]) {
                st.push(list<int>{i});
            } else if (nums[i] == nums[st.top().back()]) {
                st.top().push_back(i);
            } else {
                while (!st.empty() && nums[i] > nums[st.top().back()]) {
                    list<int> tmp = st.top();
                    st.pop();
                    int left = st.empty() ? -1 : st.top().back();
                    int right = i;
                    if (left == -1) {
                        continue;
                    }
                    int w = right - left - 1;
                    int h = min(nums[left], nums[right]) - nums[tmp.back()];
                    res += w * h;
                }
                if (st.empty() || nums[st.top().back()] != nums[i]) {
                    st.push(list<int>{i});
                } else {
                    st.top().push_back(i);
                }
            }
        }
        return res;
    }
};

【例2】柱状图中的最大矩形

【思路】

  1. 这题与接雨水相反，是要找到每个元素左右两边比它小的元素的下标。
  2. 如何求最大的元素呢？我们可以这么想，每个元素的高度可以往左右延申多宽，用它的宽度 × 这个元素的高度就是这个元素所能延申最大的面积，遍历求出每个元素所能延申的最大面积就能求出整个的最大面积了。
  3. 那么问题就转变成如何求每个元素的最大延申宽度，那么我们找到左右比它小的元素的下标，再用right - left - 1即是最大延伸宽度，如果左右不存在比它小的元素，则令left = - 1，right = height.size()即可。
class Solution {
public:
    map<int, pair<int, int>> getRes(vector<int> &nums) {
        stack<list<int>> st;
        map<int, pair<int, int>> res;
        //遍历阶段
        for (int i = 0; i < nums.size(); ++i) {
            if (st.empty() || nums[i] > nums[st.top().back()]) {
                st.push(list<int>{i});
            } else if (nums[i] == nums[st.top().back()]) {
                st.top().push_back(i);
            } else {
                while (!st.empty() && nums[i] < nums[st.top().back()]) {
                    list<int> tmp = st.top();
                    st.pop();
                    int left = st.empty() ? -1 : st.top().back();
                    for (int k : tmp) {
                        res[k] = {left, i};
                    }
                }
                if (st.empty() || nums[i] != nums[st.top().back()]) {
                    st.push(list<int>{i});
                } else {
                    st.top().push_back(i);
                }
            }
        }
        //清算结点
        while (!st.empty()) {
            list<int> tmp = st.top();
            st.pop();
            int left = st.empty() ? -1 : st.top().back();
            for (int k : tmp) {
                int left = st.empty() ? -1 : st.top().back();
                res[k] = {left, -1};
            }
        }
        return res;
    }
    int largestRectangleArea(vector<int>& heights) {
        map<int, pair<int, int>> map = getRes(heights);
        int res = INT32_MIN;
        for (int i = 0; i < heights.size(); ++i) {
            int left = map[i].first;
            int right = map[i].second == -1 ? heights.size(): map[i].second;
            res = max(res, (right - left - 1) * heights[i]);
        }
        return res;
    }
};
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)

12.单调栈——解决接雨水和柱状图中的最大矩形等问题 的相关文章

  • yolo|使输出的结果txt含目标的四个坐标信息及类别置信度

    最近参加的智能船舶挑战赛对结果的格式要求 xff1a 包含目标边界框从左上角开始的顺时针标注点坐标 xff0c 目标类别以及目标类别分数 xff0c 并用空格分开 如下图所示 xff1a 故对yolov5的detect py进行修改 xff

  • 平台开发——安装海康摄像头（2402系列球机）并实现对其RTSP的推流

    本次购入了一台海康2402系列球机 xff08 DS 2DC2402IW D3 W xff09 xff0c 对设备进行了激活 设置及简要操作 xff0c 在服务器上对其进行了推流 购买摄像头 本次购买了海康威视DS 2DC2402IW D3

  • TIPS：Ubuntu 系统python版本切换

    1 查看 xff08 1 xff09 查看系统中存在的python版本 xff1a ls usr bin python xff08 2 xff09 查看系统默认版本 xff1a python version 2 修改 xff08 1 xff

  • 报错：CommandNotFoundError: Your shell has not been properly configured to use ‘conda activate‘.

    新安装anaconda xff0c 输入 conda activate 报错 终端输入 xff1a source activate source deactivate conda activate

  • Windows下C++调用Http接口

    1 WininetHttp h span class token macro property span class token directive keyword pragma span once span span class toke

  • ubuntu系统 PyImport_ImportModule 返回 NULL

    原因 xff1a 1 python文件出错 2 python文件路径出错 在PyImport ImportModule命令前添加语句 PyRun SimpleString 34 import sys 34 PyRun SimpleStrin

  • ModuleNotFoundError:No module named

    经典报错 xff1a ModuleNotFoundError No module named XXX 但通过conda list 可以发现相关第三方包 在程序中添加路径 import sys sys path append 39 三方包路径

  • Iterator迭代器

    1 迭代器的概述 迭代器 是一种通用的遍历集合 取出集合中元素的方式 迭代器由来 集合有很多种 每种集合的数据结构是不同的 数组 链表 哈希表 集合取出元素的方式也不同 我们不可能为每种集合都定义一种取出元素的方式 浪费 所以我们就可以使用

  • strcat函数将两个字符串拼接在一起

    span class token macro property span class token directive keyword include span span class token string 34 pch h 34 span

  • 4、C语言结构体使用---链表

    结构体 1 掌握结构体的概念和用法 2 掌握结构体数组和结构体指针 3 掌握包含结构体的结构体 4 掌握结构体搭建链表方法 5 掌握结构体及链表在产品应用场景 结构体的概念 比如说学生的信息 xff0c 包含了学生名称 学号 性别 年龄等信

  • 爬虫之爬取百度贴吧

    爬虫之爬取百度贴吧 直接示例代码 xff1a import requests from lxml import html etree 61 html etree from lxml import etree class Tieba obje

  • 正则表达式匹配开头和结尾（^、$、[^指定字符]）

    1 匹配开头和结尾 代码功能 匹配字符串开头 匹配字符串结尾 示例1 xff1a 需求 xff1a 匹配以数字开头的数据 import re 匹配以数字开头的数据 match obj 61 re match 34 d 34 34 1hell

  • re.sub()用法详解

    源代码 参数及其意义 xff1a def sub pattern repl string count 61 0 flags 61 0 34 34 34 Return the string obtained by replacing the

  • BERT模型的详细介绍

    1 BERT 的基本原理是什么 xff1f BERT 来自 Google 的论文Pre training of Deep Bidirectional Transformers for Language Understanding xff0c

  • 自然语言处理(NLP)之使用TF-IDF模型计算文本相似度

    自然语言处理 NLP 之使用TF IDF模型计算文本相似度 所用数据集 xff1a ChnSentiCorp htl all csv 语料库即存放稀疏向量的列表 要注意的是 xff0c 搜索文本text与被检索的文档共用一个特征词词典 NL

  • C++中关于类重复定义的分析和解决方法

    在C 43 43 中将类以及类中的成员函数的声明放在 h的头文件中 xff0c 而将类中成员函数的定义 xff08 即实现代码 xff09 放在 cpp的源文件中 xff0c 这样我们的程序设计起来更加的模块化 xff0c 但是 xff0c

  • re.search()用法详解

    re search xff1a 匹配整个字符串 xff0c 并返回第一个成功的匹配 如果匹配失败 xff0c 则返回None pattern 匹配的规则 string 要匹配的内容 flags 标志位 这个是可选的 就是可以不写 可以写 比

  • re.findall()用法详解

    re findall xff1a 函数返回包含所有匹配项的列表 返回string中所有与pattern相匹配的全部字串 xff0c 返回形式为数组 示例代码1 xff1a 打印所有的匹配项 import re s 61 34 Long li

  • Linux系统中创建虚拟环境详解

    1 方法一 1 1 安装虚拟环境的命令 xff1a sudo pip install virtualenv sudo pip install virtualenvwrapper 1 2 安装完虚拟环境后 xff0c 如果提示找不到mkvir

  • 使用python将图片改为灰度图或黑白图

    使用python将图片改为灰度图或黑白图有三种方式 xff0c 分别是是使用cv2库和PIL库来实现 xff0c 详细过程如下所示 1 使用cv2库将图片改为灰度图 在使用cv2进行读取原彩色图片时 xff0c 在里面添加一个参数cv2 I

随机推荐

  • 虚拟机中windows镜像下载与安装

    镜像文件下载 xff1a 链接 xff1a https pan baidu com s 1VKWMHHCGRwWXk2GpxyUp0A 提取码 xff1a shlg 注意 xff1a 虚拟机中的镜像和本地电脑系统安装的镜像是一样的 安装教程

  • mongo数据库中字符串型正负数值比较大小

    数据库中数据展示 xff1a 使用python代码实现 xff1a Requires pymongo 3 6 0 43 from pymongo import MongoClient client 61 MongoClient 34 mon

  • flask项目中内部接口调用其他内部接口操作

    1 requests 在 Flask 框架项目中 xff0c 可以通过使用 requests 模块来进行内部接口调用 requests 模块是 Python 中常用的 HTTP 请求库 xff0c 可以用于发送 HTTP 请求和处理响应 示

  • ElasticSearch删除索引中的数据（delete_by_query）

    1 删除两个月以前的数据 在 Elasticsearch 中 xff0c 要删除两个月以前的数据 xff0c 可以通过以下步骤 xff1a 计算当前时间的两个月前的日期 xff0c 可以使用 Python 的 datetime 模块来实现

  • Qt Creator子图绘制

    Qt中在一个窗体文件内画所有图显然是不好维护的 xff0c 我们可以将主窗体拆分为几个子窗体 xff0c 在子窗体中绘制子图 xff0c 这样便于我们去维护我们的代码 1 在工程文件中右键 gt Add New 2 选择Qt 设计师界面 3

  • MessageFilter [target=odom ]: Dropped 100.00% of messages so far.问题解决

    错误提示 WARN 1580994954 426403779 MessageFilter target 61 odom Dropped 100 00 of messages so far Please turn the ros gmappi

  • 电磁循迹智能车基于stm32cubeMX、HAL库—我的第一辆智能车

    我的第一辆智能车 电磁循迹智能车 提示 本文适用于初学 想完成一个基础四轮车练练手者 大佬还请勿喷 不过欢迎提出意见 有纰漏之处我将及时纠正 注 工程代码链接已贴在文末 前言 所用到的硬件平台 stm32f103c8t6 舵机 电机 L29

  • 2022年国赛建模B题思路与程序

    B题 无人机遂行编队飞行中的纯方位无源定位 关键词搜索 xff1a 无人机 xff0c 无源定位 其实这个工作特别多 xff0c 知网一堆 xff0c 如果选这个题一定要想好做的出彩 xff0c 另外网上的场景和本题不是很一样 xff0c

  • 2017全国大学生电子设计竞赛:室内可见光定位装置

  • 基于FreeRTOS下多任务的同时操作

    FreeRTOS移植及多任务的实现 前言 xff1a 一 FreeRTOS移植 xff08 1 xff09 移植准备工作 xff08 2 xff09 FreeRTOS移植到stm32中 xff08 3 xff09 例程验证 二 多任务实现

  • undefined symbol 问题解决记录

    历经一个月 xff0c 昨日完成打印机network部分的编写 c语言 xff0c 编写makefile构建动态库 构建完成后遂进行调用测试 xff0c 出现 xff1a network symbol lookup error usr li

  • 2.O(NlogN)的排序算法

    认识O NlogN 的排序算法 1 剖析递归行为及其时间复杂度的估算 递归过程 xff1a 递归过程是一个多叉树 xff0c 计算所有树的结点的过程就是利用栈进行后序遍历 xff0c 每个结点通过自己的所有子结点给自己汇总信息之后才能继续向

  • 4.二叉树的遍历(C++版)

    二叉树的递归 1 二叉树递归遍历 二叉树的递归序 递归序过程 xff1a 两个注释1之间的代码代表第一次来到一个节点的时候 xff0c 会判断一下这个节点是否为空 xff1b 来到这个节点的左树去遍历 遍历完第二次回到本函数 xff0c 进

  • 6.暴力递归转动态规划

    动态规划 1 什么是动态规划 xff1f 动态规划就是暴力递归 xff08 回溯 xff09 的过程中有重复调用的过程 xff0c 动态规划在算过每次调用后把答案记下来 xff0c 下次再遇到重复过程直接调用这个行为就叫动态规划 动态规划就

  • 8.岛问题

    岛问题 题目 一个矩阵中只有0和1两种值 xff0c 每个位置都可以和自己的上 下 左 右四个位置相连 xff0c 如果有一片1连在一起 xff0c 这个部分叫做一个岛 xff0c 求一个矩阵中有多少个岛 xff1f 例子 0 0 1 0

  • 9.KMP算法

    KMP算法 1 KMP算法解决的问题 字符串str1和str2 xff0c str1是否包含str2 xff0c 如果包含返回str2在str1中开始的位置 xff0c 如果不包含返回 1 如果做到时间复杂度O N 完成 xff1f 测试用

  • 10.Manacher算法（用于解决回文子串问题）

    Manacher算法 1 Manacher算法解决的问题 字符串str中 xff0c 最长回文子串的长度如何求解 xff1f 如何做到时间复杂度O N 完成 xff1f 回文序列是从左往右和从右往左看一样 xff0c 如abba xff0c

  • git push代码到远程仓库，报错解决：fatal: unable to access ‘https://github.com/.......‘: OpenSSL SSL_read: Connec

    报错如下 xff1a 产生原因 xff1a 一般是这是因为服务器的SSL证书没有经过第三方机构的签署 xff0c 所以才报错解除ssl验证后 xff0c 再次git即可 解决办法输入此条git命令 xff1a git config glob

  • 11.滑动窗口的最大值——重要结构双端队列

    滑动窗口最大 xff08 小 xff09 值 1 滑动窗口最大值结构 窗口概念 xff1a 一开始窗口左边界L 有边界R都停留在数组左侧 xff0c 窗口L和R都只能往数组右边移动 xff0c 并且左边界L永远不能超过有边界R 任何时刻都能

  • 12.单调栈——解决接雨水和柱状图中的最大矩形等问题

    单调栈 1 单调栈实现结构 单调栈解决的问题 xff1a 给你一个数组 想要用尽可能低的代价知道数组中每一个元素的左边元素比它大的或者右边元素比他大的信息是什么 如果用暴力方法 xff0c 左边遍历一次右边遍历一次 xff0c 时间复杂度为

热门标签