代码随想录第六十三天 | 单调栈:寻找 左边 / 右边 距离当前元素最近的 更小 元素的 下标(暴力,双指针,单调栈)(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); // 数组头部加入元素0
        heights.push_back(0); // 数组尾部加入元素0
        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);
            }
        }
        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); // 数组头部加入元素0
        heights.push_back(0); // 数组尾部加入元素0
        st.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()]) { // 注意是while
                    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];
                        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、代码随想录主要题目结束

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

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

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

vite构建项目不能使用require解决方案

在utils文件夹下创建一个getImgUrl.ts文件 /** vite的特殊性, 需要处理图片 */ export const require (imgPath: string) > {try {const handlePath imgPath.replace(, ..)console.log(handlePath::, imgPath)return new URL(handlePath, import.meta.url).href} catch (…

约束概念和分类、运用

约束的概念&#xff1a; 1. 约束是作用于表列上的规则&#xff0c;用于限制加入表的数据 2.约束的存在保证了数据库中数据的正确性&#xff0c;有效性和完整性。 约束的分类&#xff1a; 非空约束&#xff1a;NOT NULL 唯一约束&#xff1a;UNIQUE 主键约束&#xff1a;PRIMARY…

01-论文阅读-Deep learning for anomaly detection in log data: a survey

01-论文阅读-Deep learning for anomaly detection in log data: a survey 文章目录 01-论文阅读-Deep learning for anomaly detection in log data: a survey摘要I 介绍II 背景A 初步定义B 挑战 III 调查方法A 搜索策略B 审查的功能 IV 调查结果A 文献计量学B 深度学习技术C …

leetcode算法之分治-归并

目录 1.排序数组2.数组中的逆序对3.计算右侧小于当前元素的个数4.翻转对 1.排序数组 排序数组 //分治-归并 class Solution {int tmp[50010]; public:vector<int> sortArray(vector<int>& nums) {mergeSort(nums,0,nums.size()-1);return nums;}void mergeS…

线程池简介及其简单实现

如果需要频繁的创建销毁线程, 就需要想办法降低创建和销毁的开销, 而线程池就是一个很好的选择: 提前创建好一些线程, 等到需要使用线程的时候, 直接从池子里拿一个就好了, 当不再使用该线程时, 就放回到池子里. 那么此时就从 创建/销毁线程 -> 池子里取线程/将线程还到池子…

找不到vcruntime140_1.dll,无法继续执行代码怎么办?5个可以解决的方案分享

在计算机使用过程中&#xff0c;我们经常会遇到一些错误提示&#xff0c;其中之一就是“VCRuntime140_1.dll缺失”。这个错误通常会导致某些应用程序无法正常运行。为了解决这个问题&#xff0c;我们需要进行修复操作。本文将介绍5个修复VCRuntime140_1.dll缺失的方法&#xff…

解锁电力安全密码:迅软DSE助您保护机密无忧

电力行业信息化水平不断提高&#xff0c;明显提升了电力企业的生产运营能力&#xff0c;然而随着越来越多重要信息存储在终端计算机中&#xff0c;电力面临的信息安全挑战也越来越多。 作为关键基础设施的基础&#xff0c;电力企业各部门产生的资料文档涵盖着大量机密信息&…

微信小程序 prettier 格式化

一、安装prettier插件 二、打开设置 然后再打开setting.json 新增代码 {"editor.formatOnSave": true,"editor.defaultFormatter": "esbenp.prettier-vscode","prettier.documentSelectors": ["**/*.wxml", "**/*.wx…

基于AVR单片机的移动目标视觉追踪系统设计与实现

基于AVR单片机的移动目标视觉追踪系统是一种常见的应用领域&#xff0c;旨在通过摄像头采集图像数据并使用图像处理和追踪算法实现对移动目标的实时追踪。本文将介绍基于AVR单片机的移动目标视觉追踪系统的设计原理和实现步骤&#xff0c;并提供相应的代码示例。 1. 设计概述 …

革新突破!智能指标平台引领时代,国产大模型与企业级部署的完美结合

11月21日&#xff0c;跬智信息&#xff08;Kyligence&#xff09;圆满召开了线上数智论坛暨产品发布会&#xff0c;升级智能一站式指标平台 Kyligence Zen 及 AI 数智助理 Kyligence Copilot 的一系列企业级能力&#xff0c;包括正式支持智谱 AI、百川智能等在内的多款国产大模…

SVN创建分支

一 从本地创建方式可指定版本号进行分支创建。 1、在本地目录右击 -----> 点击branch/tag(分支/标签) From: 源&#xff0c;可指定具体的版本号&#xff0c; To path: 可通过"..."选择分支路径 最后点击确定&#xff0c;交由服务器执行创建。 二 通过SVN客…

List操作的一些常见问题

文章目录 阿里巴巴开发手册强制规约&#xff1a;1. Arrays.asList转换基本类型数组2. Arrays.asList返回的List不支持增删操作3. 对原始数组的修改会影响到我们获得的那个List4. ArrayList.subList强转ArrayList导致异常5. ArrayList中的subList切片造成OOM6.Copy-On-Write 是什…

上海亚商投顾:北证50指数大涨 机器人概念股掀涨停潮

上海亚商投顾前言&#xff1a;无惧大盘涨跌&#xff0c;解密龙虎榜资金&#xff0c;跟踪一线游资和机构资金动向&#xff0c;识别短期热点和强势个股。 一.市场情绪 三大指数昨日震荡反弹&#xff0c;黄白二线有所分化&#xff0c;题材热点轮动表现。北证50指数大涨超3%&#…

「MACOS限定」 如何将文件上传到GitHub仓库

介绍 本期讲解&#xff1a;如何在苹果电脑上上传文件到github远程仓库 注&#xff1a;写的很详细 方便我的朋友可以看懂操作步骤 第一步 在电脑上创建一个新目录&#xff08;文件夹&#xff09; 注&#xff1a;创建GitHub账号、新建github仓库、git下载的步骤这里就不过多赘…

股票统计信息(七)

7-统计信息 文章目录 7-统计信息一. 股票周级别统计信息二. 查询可支持的所有的股票资金类型三. 股票图形统计信息四. 查询当前用户自选表里面最近十天的交易信息五. 查看天/星期范围统计的历史记录六. 查看最近多少天某个属性的涨跌幅度值 一. 股票周级别统计信息 接口描述: …

使用Python处理ADC激光测距数据并绘制为图片(二)

使用Python处理ADC激光测距数据并绘制为图片 说明一、定义全局变量变二、保存和清空原始数据三、拆分原始数据为键值对四、获取标题、FigText、更新统计信息文件五、生成图片六、处理原始数据文件七、主函数入口八、测试结果 说明 1. 主要是将ADC激光测距叠加后的1024Byte数据绘…

【码神之路】【Golang】博客网站的搭建【学习笔记整理 持续更新...】

介绍 一个用原生GO开发的博客网站&#xff0c;涉及Golang Web开发、Web服务器搭建和HTTP请求处理、模板与静态资源处理等 技术栈 后端&#xff1a;Go、Go并发机制前端&#xff1a;HTML模版链接直达 Golang搭建博客网站的学习视频 注&#xff1a;这里我只记录我实质✅学习到…

PyCharm玩转ESP32

想必玩ESP32的童鞋都知道Thonny&#xff0c;当然学Python的童鞋用的更多的可能是PyCharm和VsCode Thonny和PyCharm的对比 对于PyCharm和VsCode今天不做比较&#xff0c;今天重点说一下用PyCharm玩转ESP32&#xff0c;在这之前我们先对比下Thonny和PyCharm的优缺点 1、使用Tho…

引迈-JNPF低代码项目技术栈介绍

从 2014 开始研发低代码前端渲染&#xff0c;到 2018 年开始研发后端低代码数据模型&#xff0c;发布了JNPF开发平台。 谨以此文针对 JNPF-JAVA-Cloud微服务 进行相关技术栈展示&#xff1a; 1. 项目前后端分离 前端采用Vue.js&#xff0c;这是一种流行的前端JavaScript框架&a…

webpack 配置

1、基础配置 // node js核心模塊 const path require(path) // 插件是需要引入使用的 const ESLintPlugin require(eslint-webpack-plugin) // 自动生成index.html const HtmlWebpackPlugin require(html-webpack-plugin); // 将css文件单独打包&#xff0c;在index.html中…