代码随想录第六十三天 | 单调栈:寻找 左边 / 右边 距离当前元素最近的 更小 元素的 下标(暴力,双指针,单调栈)(84);代码随想录主要题目结束

1、寻找 左边 / 右边 距离当前元素最近的 更小 元素的 下标

1.1 leetcode 84:柱状图中最大的矩形

第一遍代码思路错了,如:输入[2,1,2],对于2,因为比栈顶元素1大,然后就会直接得出2(1,2),但是其实之前那个1也是可以用的,如果使用2,1,2就会得出3

错误思路:
单调栈内从栈顶到栈底 递增,因为除非加入的元素本身比所有可能的最大矩阵还大,不然后续计算就不需要管比栈顶元素大的元素

当加入的元素比栈顶大的时候:要比较自己的大小,之前最大矩阵的大小 和 与栈顶元素组成新的矩阵与最大矩阵加上自己后的大小,再考虑入不入栈
如果碰到等于栈顶元素的,直接不用入栈,因为对矩阵的高度不会产生影响,直接加一个栈顶元素即可
如果碰到小于栈顶元素的,比较自己加入后有没有使最大矩阵变大(高度变低长度加一),有就入栈更新最大矩阵,没有直接不入

碰到小于栈顶元素的情况:比较自己加入后有没有使最大矩阵变大(高度变低长度加一),有就更新最大矩阵,有或者没有都直接入栈
但是发现对于栈内从栈顶到栈底递增的单调栈来说,没有办法计算加入之后的矩阵,因为不知道上一个比自己小的元素是谁
再构建一个从栈顶到栈底单调递减的栈,这个栈单纯找到左边第一个更小的元素的下标即可

if(res == mat1) 加入的元素本身比所有可能的最大矩阵还大,直接清空栈加入这个元素

class Solution {
public:int largestRectangleArea(vector<int>& heights) {/*单调栈内从栈顶到栈底 递增,因为除非加入的元素本身比所有可能的最大矩阵还大,不然后续计算就不需要管比栈顶元素大的元素当加入的元素比栈顶大的时候:要比较自己的大小,之前最大矩阵的大小 和 与栈顶元素组成新的矩阵与最大矩阵加上自己后的大小,再考虑入不入栈如果碰到等于栈顶元素的,直接不用入栈,因为对矩阵的高度不会产生影响,直接加一个栈顶元素即可如果碰到小于栈顶元素的,比较自己加入后有没有使最大矩阵变大(高度变低长度加一),有就入栈更新最大矩阵,没有直接不入*/if(heights.size() == 0) return 0;int res = heights[0];stack<int> st;st.push(0);stack<int> st2;//栈顶到栈底递减 单调栈st2.push(heights.size() - 1);vector<int> getMin(heights.size(), -1);//找左边更小元素的下标for(int i = heights.size() - 2; i >= 0; i--) {while(!st2.empty() && heights[i] < heights[st2.top()]) {getMin[st2.top()] = i;st2.pop();}st2.push(i);}for(int i = 1; i < heights.size(); i++) {if(heights[i] == heights[st.top()]) {res += heights[i];}else if(heights[i] > heights[st.top()]) {int mat1 = heights[i];int mat2 = res;int mat3 = heights[st.top()] * (i - st.top() + 1);res = max(mat1, max(mat2, mat3));if(res == mat1) {//加入的元素本身比所有可能的最大矩阵还大,直接清空栈加入这个元素while(!st.empty()) {st.pop();}st.push(i);}}else {st.push(i);/*比较自己加入后有没有使最大矩阵变大(高度变低长度加一),有就更新最大矩阵,有或者没有都直接入栈但是发现对于栈内从栈顶到栈底递增的单调栈来说,没有办法计算加入之后的矩阵,因为不知道上一个比自己小的元素是谁再构建一个从栈顶到栈底单调递减的栈,这个栈单纯找到左边第一个更小的元素的下标即可*/int mat = 0;if(getMin[st.top()] == -1) {mat = heights[i] * (i + 1);}else {mat = heights[i] * (i - getMin[st.top()]);}if(res < mat) {res = mat;}}}return res;}
};

1.2 leetcode 84:暴力解法

其实跟昨天 leetcode 42:接雨水 思路差不多都是左右找元素不同的是找到 左边 / 右边 第一个 更小的 元素矩阵的高是由当前元素决定的(最高的)宽度是右边减左边减一即可

然后把矩阵中最大的那个记录就行

class Solution {
public:int largestRectangleArea(vector<int>& heights) {int sum = 0;for (int i = 0; i < heights.size(); i++) {int left = i;int right = i;for (; left >= 0; left--) {if (heights[left] < heights[i]) break;}for (; right < heights.size(); right++) {if (heights[right] < heights[i]) break;}int w = right - left - 1;int h = heights[i];sum = max(sum, w * h);}return sum;}
};

1.3 leetcode 84:双指针解法

根据思路写代码:
记录左边 第一个 更小的节点 下标vector<int> leftMin(heights.size(), -1);
记录右边 第一个 更小的节点 下标vector<int> rightMin(heights.size(), -1);
注意数组记录的是 下标 不是元素值

注意跟 leetcode 42:接雨水 不同不是找左边最大值了,找最近的更小的值,所以不是用if,而是不断向左遍历更小元素。寻找的过程中,一旦小了就停,而且记录的是 下标 不是 数值大小

for(int i = 1; i < heights.size(); i++) {int t = i - 1;while(t >= 0 && heights[t] >= heights[i]) {t = leftMin[t];}leftMin[i] = t;
}

完整代码:

class Solution {
public:int largestRectangleArea(vector<int>& heights) {vector<int> leftMin(heights.size(), -1);//记录左边第一个更小的节点 下标vector<int> rightMin(heights.size(), -1);//记录右边第一个更小的节点 下标//注意数组记录的是下标不是元素值for(int i = 1; i < heights.size(); i++) {//注意跟 leetcode 42:接雨水 不同,不是找左边最小值了,找最近的更小的值,所以不是用if,而是不断向左遍历更小元素寻找的过程,一旦小了就停int t = i - 1;while(t >= 0 && heights[t] >= heights[i]) {t = leftMin[t];}leftMin[i] = t;}for(int i = heights.size() - 2; i >= 0; i--) {int t = i + 1;while(t < heights.size() && heights[t] >= heights[i]) {t = rightMin[t];}if(t < heights.size()) {rightMin[i] = t;}else {rightMin[i] = -1;}}int res = 0;for(int i = 0; i < heights.size(); i++) {int left = 0;if(leftMin[i] == -1) {left = -1;}else {left = leftMin[i];}int right = 0;if(rightMin[i] == -1) {right = heights.size();}else {right = rightMin[i];}int s = heights[i] * (right - left - 1);res = max(res, s);}return res;}
};

代码随想录思路及代码:
本题双指针的写法整体思路leetcode 42:接雨水 是一致的,但要比 leetcode 42:接雨水 难一些
难就难在本题要记录记录每个柱子 左边第一个 小于 该柱子的下标,而不是左边第一个小于该柱子的高度
所以需要循环查找,也就是下面在寻找的过程中使用了while

class Solution {
public:int largestRectangleArea(vector<int>& heights) {vector<int> minLeftIndex(heights.size());vector<int> minRightIndex(heights.size());int size = heights.size();// 记录每个柱子 左边第一个小于该柱子的下标minLeftIndex[0] = -1; // 注意这里初始化,防止下面while死循环for (int i = 1; i < size; i++) {int t = i - 1;// 这里不是用if,而是不断向左寻找的过程while (t >= 0 && heights[t] >= heights[i]) t = minLeftIndex[t];minLeftIndex[i] = t;}// 记录每个柱子 右边第一个小于该柱子的下标minRightIndex[size - 1] = size; // 注意这里初始化,防止下面while死循环for (int i = size - 2; i >= 0; i--) {int t = i + 1;// 这里不是用if,而是不断向右寻找的过程while (t < size && heights[t] >= heights[i]) t = minRightIndex[t];minRightIndex[i] = t;}// 求和int result = 0;for (int i = 0; i < size; i++) {int sum = heights[i] * (minRightIndex[i] - minLeftIndex[i] - 1);result = max(sum, result);}return result;}
};

1.4 leetcode 84:单调栈

本题单调栈的解法和接雨水的题目遥相呼应
为什么这么说呢,leetcode 42:接雨水 是找每个柱子左右两边第一个大于该柱子高度的柱子,而本题是找每个柱子左右两边第一个小于该柱子的柱子

根据思路写代码报错:

class Solution {
public:int largestRectangleArea(vector<int>& heights) {//递减的单调栈,等发现当前元素大于栈顶元素,说明找到右边第一个更大的了int res = heights[0];stack<int> st; st.push(0);for(int i = 1; i < heights.size(); i++) {if(heights[i] >= heights[st.top()]) {st.push(i);}else {while (!st.empty() && heights[i] < heights[st.top()]) { int mid = st.top();st.pop();if (!st.empty()) {int left = st.top();int right = i;int w = right - left - 1;int h = heights[mid];res = max(res, w * h);}}st.push(i);}}//对于剩下的在栈内递减的元素的处理if(!st.empty()) {int rightIndex = st.top();while(st.size() > 1) {st.pop();}int leftIndex = st.top();int mat_s2 = heights[st.top()] * (rightIndex - leftIndex + 1);if(res < mat_s2) res = mat_s2;}return res;}
};

对剩下的在栈内的元素处理出了问题,因为不一定是最小的那个元素乘以长度就是最大,还可能是某几个连续元素画矩阵最大
还是在头尾加两个0元素靠谱,这样保证所有非0元素都可以被计算过

对于这段代码一开始没理解,说明之前暴力双指针的部分也没理解透:为什么矩阵的高是三个元素中的最大值,以[2,1,5,6,2,3]为例,其实对于5、6,遍历到2的时候,其实算了两次才到10;先算的6,结果6;然后算的5,5*2才是最终结果10,矩阵的高其实是栈中最高的那个元素的大小

else {while (!st.empty() && heights[i] < heights[st.top()]) { int mid = st.top();st.pop();if (!st.empty()) {int left = st.top();int right = i;int w = right - left - 1;int h = heights[mid];res = max(res, w * h);}}st.push(i);
}

修改后的完整代码如下:

class Solution {
public:int largestRectangleArea(vector<int>& heights) {//递减的单调栈,等发现当前元素大于栈顶元素,说明找到右边第一个更大的了heights.insert(heights.begin(), 0); // 数组头部加入元素0heights.push_back(0); // 数组尾部加入元素0int res = heights[0];stack<int> st; st.push(0);for(int i = 1; i < heights.size(); i++) {if(heights[i] >= heights[st.top()]) {st.push(i);}else {while (!st.empty() && heights[i] < heights[st.top()]) { int mid = st.top();st.pop();if (!st.empty()) {int left = st.top();int right = i;int w = right - left - 1;int h = heights[mid];res = max(res, w * h);}}st.push(i);}}return res;}
};

代码随想录详细思路:
本地单调栈的解法和接雨水的题目是遥相呼应的
为什么这么说呢,leetcode 42:接雨水 是找每个柱子左右两边第一个大于该柱子高度的柱子,而本题是找每个柱子左右两边第一个小于该柱子的柱子

这里就涉及到了单调栈很重要的性质,就是单调栈里的顺序,是从小到大还是从大到小
在 leetcode 42:接雨水 中我讲解了接雨水的单调栈从栈头(元素从栈头弹出)到栈底的顺序应该是从小到大的顺序
那么因为本题是要找每个柱子左右两边第一个小于该柱子的柱子,所以从栈头(元素从栈头弹出)到栈底的顺序应该是从大到小的顺序

举一个例子,如图:
要找每个柱子左右两边第一个小于该柱子的柱子
只有栈里从大到小的顺序,才能保证栈顶元素找到左右两边第一个小于栈顶元素的柱子
所以本题单调栈的顺序正好与接雨水反过来

此时大家应该可以发现其实就是栈顶和栈顶的下一个元素以及要入栈的 一共三个元素组成了我们要求最大面积的高度和宽度
除了栈内元素顺序和接雨水不同,剩下的逻辑就都差不多了
主要就是分析清楚如下三种情况:
情况一:当前遍历的元素heights[i]大于栈顶元素heights[st.top()]的情况
情况二:当前遍历的元素heights[i]等于栈顶元素heights[st.top()]的情况
情况三:当前遍历的元素heights[i]小于栈顶元素heights[st.top()]的情况

代码随想录C++代码如下:

class Solution {
public:int largestRectangleArea(vector<int>& heights) {int result = 0;stack<int> st;heights.insert(heights.begin(), 0); // 数组头部加入元素0heights.push_back(0); // 数组尾部加入元素0st.push(0);// 第一个元素已经入栈,从下标1开始for (int i = 1; i < heights.size(); i++) {if (heights[i] > heights[st.top()]) { // 情况一st.push(i);} else if (heights[i] == heights[st.top()]) { // 情况二st.pop(); // 这个可以加,可以不加,效果一样,思路不同st.push(i);} else { // 情况三while (!st.empty() && heights[i] < heights[st.top()]) { // 注意是whileint mid = st.top();st.pop();if (!st.empty()) {int left = st.top();int right = i;int w = right - left - 1;int h = heights[mid];result = max(result, w * h);}}st.push(i);}}return result;}
};

首先来说末尾为什么要加元素0

如果数组本身就是升序的,例如[2,4,6,8],那么入栈之后 都是单调递减一直都没有走 情况三 计算结果的那一步,所以最后输出的就是0了。 如图:
数组本身就是升序,一直都没有走 情况三 计算结果的哪一步
那么结尾加一个0,就会让栈里的所有元素,走到情况三的逻辑

开头为什么要加元素0?
如果数组本身是降序的,例如 [8,6,4,2],在 8 入栈后,6 开始与8 进行比较,此时我们得到 mid(8),rigt(6),但是得不到 left
(mid、left,right 都是对应代码随想录实现代码里的逻辑)
因为 将 8 弹出之后,栈里没有元素了,那么为了避免空栈取值,直接跳过了计算结果的逻辑
之后又将6 加入栈(此时8已经弹出了),然后 就是 4 与 栈口元素 8 进行比较,周而复始,那么计算的最后结果result就是0。 如图所示:
数组本身是降序的,为了避免空栈取值,直接跳过了计算结果的逻辑
所以我们需要在 height数组前后各加一个元素0

2、代码随想录主要题目结束

曲曲折折写到这里,人间忽晚,山河已秋
其实也就三个月不到

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/199878.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

PaaS、 IaaS 和 SaaS 的区别

我感觉我有点捂了 iaas&#xff0c;paas&#xff0c;和saas的区别&#xff0c;以及他们啥意思了 简单说就是&#xff0c;一个公司有很多项目&#xff0c;要管理这些项目&#xff0c;每个项目都有很多组成部分需要管理的地方&#xff0c;例如&#xff0c;存储代码&#xff0c;例…

HTML5学习系列之项目实战1

HTML5学习系列之项目实战1 前言代码记录问题总结 前言 学习记录 代码 <div id"player"><audio id"musicbox"></audio><div id"controls" class"clearfix controls"><div id"play" class"…

uniapp中实现圆形进度条的方式有哪些?

前言 在uniapp开发小程序或者apk时&#xff0c;页面需要用到一个圆形进度条&#xff08;带文字和百分比的&#xff09;&#xff0c;自己也自定义过一个,但是有一点小问题&#xff0c;咱先展示如何引入插件市场的在介绍自定义的&#xff01;一共四种&#xff0c;但是你需要考虑自…

高压放大器使用方法介绍

高压放大器是一种用于放大高压信号的电子设备&#xff0c;常用于科学研究、工业应用和医疗设备等领域。它可以将低电压信号放大到较高的电压水平&#xff0c;以满足特定应用的需求。 使用高压放大器需要注意以下几个方面&#xff1a; 1.了解设备规格&#xff1a;在使用高压放大…

0时区格林威治时间转换手机当地时间-Android

假设传入的是2023-11-01T12:59:10.420987这样的格式 要将格式为2023-11-01T12:59:10.420987的UTC时间字符串转换为Android设备本地时间&#xff0c;您可以使用java.time包中的类&#xff08;在API 26及以上版本中可用&#xff09;。如果您的应用需要支持较低版本的Android&…

【外汇天眼】交易之路:从无知到觉醒,揭秘成功交易员的五个成长阶段

世界顶尖交易员的成功背后隐藏的真正秘诀引人瞩目。许多人梦想着像电影中的主角一样&#xff0c;成为一名成功的金融交易员。尽管开设交易账户相对简单&#xff0c;但要达到稳定盈利的境界确实非常不容易。众所周知&#xff0c;在衍生品市场中&#xff0c;有80%甚至90%以上的交…

网络安全涉及哪些方面?

1.系统安全&#xff1a;运行系统安全即保证信息处理和传输系统的安全。它侧重于保证系统正常运行&#xff0c;避免因为系统的损坏而对系统存储、处理和传输的消息造成破坏和损失&#xff0c;避免由于电磁泄露&#xff0c;产生信息泄露&#xff0c;干扰他人或受他人干扰。 2. 网…

docker部署jdk21的镜像

docker Docker是一种开放源代码软件&#xff0c;可以帮助开发人员更轻松地创建、部署和运行应用程序。它是一种容器化技术&#xff0c;可以将应用程序及其依赖项打包在一个容器中&#xff0c;从而使应用程序更加便携和可移植。Docker将操作系统、应用程序和硬件虚拟化进行了彻底…

基于单片机设计的气压与海拔高度检测计(采用MPL3115A2芯片实现)

一、前言 随着科技的不断发展&#xff0c;在许多领域中&#xff0c;对气压与海拔高度的测量变得越来越重要。例如&#xff0c;对于航空和航天工业、气象预报、气候研究等领域&#xff0c;都需要高精度、可靠的气压与海拔高度检测装置。针对这一需求&#xff0c;基于单片机设计…

2023年中国聚氨酯树脂涂料需求量、市场规模及行业趋势分析[图]

聚氨酯是一种新兴的有机高分子材料&#xff0c;被誉为“第五大塑料”&#xff0c;因其卓越的性能而被广泛应用于国民经济众多领域。产品应用领域涉及轻工、化工、电子、纺织、医疗、建筑、建材、汽车、国防、航天、航空等。2022年中国聚氨酯产量已达1600万吨。 2012-2022年中国…

从傅里叶变换,到短时傅里叶变换,再到小波分析(CWT),看这一篇就够了(附MATLAB傻瓜式实现代码)

本专栏中讲了很多时频域分析的知识&#xff0c;不过似乎还没有讲过时频域分析是怎样引出的。 所以本篇将回归本源&#xff0c;讲一讲从傅里叶变换→短时傅里叶变换→小波分析的过程。 为了让大家更直观得理解算法原理和推导过程&#xff0c;这篇文章将主要使用图片案例。 一…

nginx-编译安装-基础指令-信号

nginx 的编译与安装 nginx目录介绍 如果我们需要整合第三方模块&#xff0c;需要自己编译然此模块编译到nginx里面。apt和yum的安装只具有常用的基础功能。 下载nginx wget http://nginx.org/download/nginx-1.14.0.tar.gz/auto 目录 Changes 描述了一每个版本提供了那些特…

第2关:图的深度优先遍历

任务要求参考答案评论2 任务描述相关知识编程要求测试说明 任务描述 本关任务&#xff1a;以邻接矩阵存储图&#xff0c;要求编写程序实现图的深度优先遍历。 相关知识 图的深度优先遍历类似于树的先序遍历, 是树的先序遍历的推广&#xff0c;其基本思想如下&#xff1a; …

Linux之进程概念(一)

&#x1f4d8;北尘_&#xff1a;个人主页 &#x1f30e;个人专栏:《Linux操作系统》《经典算法试题 》《C》 《数据结构与算法》 ☀️走在路上&#xff0c;不忘来时的初心 文章目录 一、冯诺依曼体系结构二、操作系统(Operator System)1、概念2、设计OS的目的3、定位4、如何理…

OceanBase:集群常见操作

目录 1.查看 OBD 管理的集群列表 2.查看某个集群状态 3.启动 OceanBase 集群 4.连接 OceanBase 集群 5.停止运行中的集群 6.销毁已部署的集群 7.查看集群配置项 8.修改集群配置项 1.查看 OBD 管理的集群列表 obd cluster list 2.查看某个集群状态 obd cluster displa…

如何利用CHATGPT写主题文章

问CHAT&#xff1a;新课标下畅言智慧课堂助力小学生量感培养&#xff0c;拟解决的关键问题 CHAT回复&#xff1a; 1. 确定智慧课堂在新课标下的正确应用方法&#xff1a;新课标对教育方法、内容等提出了新的要求&#xff0c;需要探讨如何将智慧课堂与新课标相结合&#xff0c;…

OceanBase 4.2.1 LTS 发版 | 一体化数据库首个长期支持版本

在刚刚结束的年度发布会上&#xff0c;OceanBase 沿着“一体化”产品战略思路&#xff0c;发布了一体化数据库的首个长期支持版本 4.2.1 LTS。作为 4.0 系列的第一个 LTS 版本&#xff0c;该版本的定位是支撑客户关键业务稳定长久运行&#xff0c;我们非常认真的打磨了这个版本…

单片机和FreeRTOS上跑机器人ROS的应用

机器人的应用越来越广泛了&#xff0c;大家熟知的稚晖君直接创业搞机器人&#xff0c;可想而至&#xff0c;接下来的十年&#xff0c;机器人绝对是热门的行业。 目前市面上很多机器人都是基于一套叫做ROS的系统开发的&#xff0c;今天就给大家分享一个跑在MCU上&#xff0c;基…

VScode调试没有反应

点击调试按钮后没反应 有可能是vscode中安装的python插件版本问题 可以通过重新安装比较旧一点的python尝试解决此问题 步骤如下&#xff1a; 然后从中选择比当前版本更低的版本即可 安装完成后需重启vscode

《研发效能 100 问》首发,多位专家解读「研效提升」的破局之道?

为了可以帮助更多研发管理者和研发效能负责人&#xff0c;了解构建研发效能体系应从何做起&#xff0c;以及在构建过程中需要解决哪些疑难问题&#xff0c;有哪些最佳实践可以借鉴。2023 年 7 月&#xff0c;思码逸发起&#xff0c;由行业知名研发效能专家张乐老师担任出品人&a…