代码随想录Day40-单调栈:力扣第496e、503m、42h、84h题

2023-10-30 23:30

本文主要是介绍代码随想录Day40-单调栈:力扣第496e、503m、42h、84h题,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

496e. 下一个更大元素 I

题目链接
代码随想录文章讲解链接

方法一:单调栈+哈希表

用时:13m52s

思路

维护一个栈底到栈顶是单调递减的栈,从后往前遍历数组nums2,更新栈。nums2当前元素nums2[i]的下一个更大元素就是栈顶元素,若栈顶为空则表示nums2[i]之后没有比他大的元素。用哈希表存储,然后遍历nums1时再从哈希表中获取值。

  • 时间复杂度: O ( m + n ) O(m+n) O(m+n)
  • 空间复杂度: O ( m + n ) O(m+n) O(m+n)
C++代码
class Solution {
public:vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {stack<int> stk;unordered_map<int, int> hashMap;vector<int> res(nums1.size(), 0);for (int i = nums2.size() - 1; i >= 0; --i) {while (!stk.empty() && nums2[i] > stk.top()) stk.pop();hashMap[nums2[i]] = stk.empty() ? -1 : stk.top();stk.push(nums2[i]);}for (int i = 0; i < res.size(); ++i) res[i] = hashMap[nums1[i]];return res;}
};

看完讲解的思考

无。

代码实现遇到的问题

无。


503m. 下一个更大元素II

题目链接
代码随想录文章讲解链接

方法一:单调栈

用时:16m28s

思路

维护一个栈底到栈顶单调递减的单调栈,遍历两遍数组。

  • 时间复杂度: O ( n ) O(n) O(n)
  • 空间复杂度: O ( n ) O(n) O(n)
C++代码
class Solution {
public:vector<int> nextGreaterElements(vector<int>& nums) {int size = nums.size();stack<int> stk;vector<int> res(size, -1);for (int i = 0; i < size * 2; ++i) {while (!stk.empty() && nums[stk.top()] < nums[i % size]) {res[stk.top()] = nums[i % size];stk.pop();}stk.push(i % size);}return res;}
};

看完讲解的思考

无。

代码实现遇到的问题

无。


42h. 接雨水

题目链接
代码随想录文章讲解链接

方法一:按列统计

用时:28m51s

思路

分别统计每一列雨水的高度,设某一列i左边最高的柱子高度为L,列i右边最高的柱子高度为R,若min(L,R)大于列i的高度,则列i的雨水量为min(L,R) - height[i],否则为0。
先分别记录下每个位置左右两边最高的柱子的高度,然后再统计每一列雨水的高度。

  • 时间复杂度: O ( n ) O(n) O(n)
  • 空间复杂度: O ( n ) O(n) O(n)
C++代码
class Solution {
public:int trap(vector<int>& height) {int size = height.size();vector<int> leftMax(size, 0);vector<int> rightMax(size, 0);int maxHeight = 0;int res = 0;// 记录每个位置左右两边最高的柱子高度for (int i = 0; i < size; ++i) {leftMax[i] = maxHeight;maxHeight = max(maxHeight, height[i]);}maxHeight = 0;for (int i = size - 1; i >= 0; --i) {rightMax[i] = maxHeight;maxHeight = max(maxHeight, height[i]);}// 统计每一列的雨水for (int i = 1; i < size - 1; ++i) {int minHeight = min(leftMax[i], rightMax[i]);if (minHeight > height[i]) res += minHeight - height[i];}return res;}
};

方法二:单调栈按行统计

用时:13m28s

思路

维护一个栈底到栈顶单调递减的单调栈。
遍历数组的时候,若遇到小于等于栈顶元素的元素,则直接入栈。
若遇到大于栈顶元素的元素,此时栈顶元素作为凹陷处,倒数第二个栈顶元素和当前元素作为两头的柱子,可以形成一个坑接住雨水,接住雨水的量等于(min(height[i], height[stk.top()]) - height[mid]) * (i - stk.top() - 1),分别是高乘宽。

  • 时间复杂度: O ( n ) O(n) O(n)
  • 空间复杂度: O ( n ) O(n) O(n)
C++代码
class Solution {
public:int trap(vector<int>& height) {stack<int> stk;int res = 0;for (int i = 0; i < height.size(); ++i) {while (!stk.empty() && height[i] > height[stk.top()]) {int mid = stk.top();stk.pop();if (!stk.empty()) res += (min(height[i], height[stk.top()]) - height[mid]) * (i - stk.top() - 1);}stk.push(i);}return res;}
};

看完讲解的思考

无。

代码实现遇到的问题

无。


84h. 柱状图中最大的矩形

题目链接
代码随想录文章讲解链接

方法一:三次遍历

用时:18m4s

思路

以某个柱子为基准,最大矩形面积与该柱子两侧第一个比它矮的柱子的位置有关。
前两次遍历找到每个柱子左右两侧第一个比它矮的柱子的位置。
最后一次遍历计算以各个柱子为基准的最大矩形面积,最大值即为答案。

  • 时间复杂度: O ( n ) O(n) O(n)
  • 空间复杂度: O ( n ) O(n) O(n)
C++代码
class Solution {
public:int largestRectangleArea(vector<int>& heights) {int size = heights.size();vector<int> leftMin(size);vector<int> rightMin(size);int res = 0;// 记录每个柱子左边第一个比它小的柱子的位置leftMin[0] = -1;for (int i = 1; i < size; ++i) {int left = i - 1;while (left >= 0 && heights[left] >= heights[i]) left = leftMin[left];leftMin[i] = left;}// 记录每个柱子右边第一个比它小的柱子的位置rightMin[size - 1] = size;for (int i = size - 2; i >= 0; --i) {int right = i + 1;while (right < size && heights[right] >= heights[i]) right = rightMin[right];rightMin[i] = right;}// 遍历以每个柱子为基准的矩形大小,记录最大值for (int i = 0; i < size; ++i) res = max(res, heights[i] * (rightMin[i] - leftMin[i] - 1));return res;}
};

方法二:单调栈

用时:33m9s

思路

因为我们要找到某个基准柱子左右两边比它小的柱子的位置,所以药维护一个栈底到栈顶单调递增的单调栈,这样对于栈顶元素的柱子,它左边第一个比它小的柱子就是第二个栈顶元素,右边第一个比它小的元素就是遍历过程中比栈顶元素小的元素。
遍历数组,若元素大于等于栈顶元素,则入栈;若元素小于栈顶元素,则取出栈顶元素作为基准柱子,然后弹出栈顶元素,基准柱子左边第一个比它小的柱子就是此时的栈顶元素,右边第一个比它小的柱子就是当前遍历的元素,然后记录矩形的面积并更新答案。
由于在遍历的过程中,可能会出现栈为空的情况,以及数组本身就是递增数组的情况,此时会有特殊情况需要处理,可以在数组前后各加入一个0,简化逻辑,因为0一定是小于柱子高度,能够作为左右两端最矮的基准柱子的边界。

  • 时间复杂度: O ( n ) O(n) O(n)
  • 空间复杂度: O ( n ) O(n) O(n)
C++代码
class Solution {
public:int largestRectangleArea(vector<int>& heights) {stack<int> stk;int res = 0;heights.insert(heights.begin(), 0);heights.push_back(0);stk.push(0);for (int i = 1; i < heights.size(); ++i) {while (heights[i] < heights[stk.top()]) {int mid = stk.top();stk.pop();res = max(res, heights[mid] * (i - stk.top() - 1));}stk.push(i);}return max(res, heights[stk.top()]);}
};

看完讲解的思考

无。

代码实现遇到的问题

边界问题处理了半天没搞定,在数组前后各加入一个0的方法真巧妙。


最后的碎碎念

最近都在搞比赛,好久没刷题了,比赛目前搞得差不多了,得接着刷题了。
希望比赛能拿个好成绩,求求求求求求了!

这篇关于代码随想录Day40-单调栈:力扣第496e、503m、42h、84h题的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/311264

相关文章

基于Canvas的Html5多时区动态时钟实战代码

《基于Canvas的Html5多时区动态时钟实战代码》:本文主要介绍了如何使用Canvas在HTML5上实现一个多时区动态时钟的web展示,通过Canvas的API,可以绘制出6个不同城市的时钟,并且这些时钟可以动态转动,每个时钟上都会标注出对应的24小时制时间,详细内容请阅读本文,希望能对你有所帮助...

HTML5 data-*自定义数据属性的示例代码

《HTML5data-*自定义数据属性的示例代码》HTML5的自定义数据属性(data-*)提供了一种标准化的方法在HTML元素上存储额外信息,可以通过JavaScript访问、修改和在CSS中使用... 目录引言基本概念使用自定义数据属性1. 在 html 中定义2. 通过 JavaScript 访问3.

Flutter监听当前页面可见与隐藏状态的代码详解

《Flutter监听当前页面可见与隐藏状态的代码详解》文章介绍了如何在Flutter中使用路由观察者来监听应用进入前台或后台状态以及页面的显示和隐藏,并通过代码示例讲解的非常详细,需要的朋友可以参考下... flutter 可以监听 app 进入前台还是后台状态,也可以监听当http://www.cppcn

Python使用PIL库将PNG图片转换为ICO图标的示例代码

《Python使用PIL库将PNG图片转换为ICO图标的示例代码》在软件开发和网站设计中,ICO图标是一种常用的图像格式,特别适用于应用程序图标、网页收藏夹图标等场景,本文将介绍如何使用Python的... 目录引言准备工作代码解析实践操作结果展示结语引言在软件开发和网站设计中,ICO图标是一种常用的图像

Java中有什么工具可以进行代码反编译详解

《Java中有什么工具可以进行代码反编译详解》:本文主要介绍Java中有什么工具可以进行代码反编译的相关资,料,包括JD-GUI、CFR、Procyon、Fernflower、Javap、Byte... 目录1.JD-GUI2.CFR3.Procyon Decompiler4.Fernflower5.Jav

javaScript在表单提交时获取表单数据的示例代码

《javaScript在表单提交时获取表单数据的示例代码》本文介绍了五种在JavaScript中获取表单数据的方法:使用FormData对象、手动提取表单数据、使用querySelector获取单个字... 方法 1:使用 FormData 对象FormData 是一个方便的内置对象,用于获取表单中的键值

Vue ElementUI中Upload组件批量上传的实现代码

《VueElementUI中Upload组件批量上传的实现代码》ElementUI中Upload组件批量上传通过获取upload组件的DOM、文件、上传地址和数据,封装uploadFiles方法,使... ElementUI中Upload组件如何批量上传首先就是upload组件 <el-upl

C++使用栈实现括号匹配的代码详解

《C++使用栈实现括号匹配的代码详解》在编程中,括号匹配是一个常见问题,尤其是在处理数学表达式、编译器解析等任务时,栈是一种非常适合处理此类问题的数据结构,能够精确地管理括号的匹配问题,本文将通过C+... 目录引言问题描述代码讲解代码解析栈的状态表示测试总结引言在编程中,括号匹配是一个常见问题,尤其是在

Java调用DeepSeek API的最佳实践及详细代码示例

《Java调用DeepSeekAPI的最佳实践及详细代码示例》:本文主要介绍如何使用Java调用DeepSeekAPI,包括获取API密钥、添加HTTP客户端依赖、创建HTTP请求、处理响应、... 目录1. 获取API密钥2. 添加HTTP客户端依赖3. 创建HTTP请求4. 处理响应5. 错误处理6.

使用 sql-research-assistant进行 SQL 数据库研究的实战指南(代码实现演示)

《使用sql-research-assistant进行SQL数据库研究的实战指南(代码实现演示)》本文介绍了sql-research-assistant工具,该工具基于LangChain框架,集... 目录技术背景介绍核心原理解析代码实现演示安装和配置项目集成LangSmith 配置(可选)启动服务应用场景