算法学习——LeetCode力扣单调栈篇

2024-03-30 21:52

本文主要是介绍算法学习——LeetCode力扣单调栈篇,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

算法学习——LeetCode力扣单调栈篇

在这里插入图片描述

739. 每日温度

739. 每日温度 - 力扣(LeetCode)

描述

给定一个整数数组 temperatures ,表示每天的温度,返回一个数组 answer ,其中 answer[i] 是指对于第 i 天,下一个更高温度出现在几天后。如果气温在这之后都不会升高,请在该位置用 0 来代替。

示例

示例 1:

输入: temperatures = [73,74,75,71,69,72,76,73]
输出: [1,1,4,2,1,1,0,0]

示例 2:

输入: temperatures = [30,40,50,60]
输出: [1,1,1,0]

示例 3:

输入: temperatures = [30,60,90]
输出: [1,1,0]

提示

1 <= temperatures.length <= 105
30 <= temperatures[i] <= 100

代码解析

单调栈

通常是一维数组,要寻找任一个元素的右边或者左边第一个比自己大或者小的元素的位置,此时我们就要想到可以用单调栈了。

用temperatures = [73, 74, 75, 71, 71, 72, 76, 73]为例来逐步分析,输出应该是 [1, 1, 4, 2, 1, 1, 0, 0]。

  • 首先先将第一个遍历元素加入单调栈
    在这里插入图片描述
  • 加入T[1] = 74,因为T[1] > T[0],而我们要保持一个递增单调栈(从栈头到栈底),所以将T[0]弹出,T[1]加入,此时result数组可以记录了,result[0] = 1,即T[0]右面第一个比T[0]大的元素是T[1]。
    在这里插入图片描述
  • 加入T[2],同理,T[1]弹出
    在这里插入图片描述
  • 加入T[3],T[3] < T[2] (当前遍历的元素T[i]小于栈顶元素T[st.top()]的情况),加T[3]加入单调栈。
    在这里插入图片描述
  • 加入T[4],T[4] == T[3] (当前遍历的元素T[i]等于栈顶元素T[st.top()]的情况),此时依然要加入栈,不用计算距离,因为我们要求的是右面第一个大于本元素的位置,而不是大于等于!
    在这里插入图片描述
  • 加入T[5],T[5] > T[4] (当前遍历的元素T[i]大于栈顶元素T[st.top()]的情况),将T[4]弹出,同时计算距离,更新result

在这里插入图片描述

  • T[4]弹出之后, T[5] > T[3] (当前遍历的元素T[i]大于栈顶元素T[st.top()]的情况),将T[3]继续弹出,同时计算距离,更新result

在这里插入图片描述
直到发现T[5]小于T[st.top()],终止弹出,将T[5]加入单调栈
在这里插入图片描述
加入T[6],同理,需要将栈里的T[5],T[2]弹出
在这里插入图片描述

  • 同理,继续弹出
    在这里插入图片描述
  • 此时栈里只剩下了T[6]
    在这里插入图片描述
  • 加入T[7], T[7] < T[6] 直接入栈,这就是最后的情况,result数组也更新完了。
  • 在这里插入图片描述

那result[6] , result[7]怎么没更新啊,元素也一直在栈里。

其实定义result数组的时候,就应该直接初始化为0,如果result没有更新,说明这个元素右面没有更大的了,也就是为0。

class Solution {
public:vector<int> dailyTemperatures(vector<int>& temperatures) {vector<int> result(temperatures.size(),0);stack<int> st;st.push(0);for(int i=1 ; i<temperatures.size(); i++){while( st.empty()==0  &&  temperatures[i] > temperatures[st.top()] ){result[st.top()] = i - st.top();st.pop();}st.push(i);}return result;}
};

496. 下一个更大元素 I

496. 下一个更大元素 I - 力扣(LeetCode)

nums1 中数字 x 的 下一个更大元素 是指 x 在 nums2 中对应位置 右侧 的 第一个 比 x 大的元素。

描述

给你两个 没有重复元素 的数组 nums1 和 nums2 ,下标从 0 开始计数,其中nums1 是 nums2 的子集。

对于每个 0 <= i < nums1.length ,找出满足 nums1[i] == nums2[j] 的下标 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 。

示例 2:

输入:nums1 = [2,4], nums2 = [1,2,3,4].
输出:[3,-1]
解释:nums1 中每个值的下一个更大元素如下所述:

  • 2 ,用加粗斜体标识,nums2 = [1,2,3,4]。下一个更大元素是 3 。
  • 4 ,用加粗斜体标识,nums2 = [1,2,3,4]。不存在下一个更大元素,所以答案是 -1 。

提示

1 <= nums1.length <= nums2.length <= 1000
0 <= nums1[i], nums2[i] <= 104
nums1和nums2中所有整数 互不相同
nums1 中的所有整数同样出现在 nums2 中

代码解析

和 739 完全一样

  • 739是找每一个点的右边第一个大于点
  • 该题是找部分点(num1)的右边第一个最大点

具体步骤

  • 用map记录num1出现的点
  • 然后和739一样找每一个右边第一个最大值
  • 找到后判断该点是否是num1里面的,是就保存,不是就放弃
  • 此处和739不同,739找到就保存
class Solution {
public:vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {vector<int> result(nums1.size(),-1);stack<int> st;unordered_map<int,int> umap;for(int i=0 ; i<nums1.size(); i++){umap[nums1[i]] = i; }// for(auto it:umap) cout<<it.first<<' '<<it.second<<endl;st.push(0);for(int i=1 ;i<nums2.size();i++){while(st.empty()==0 && nums2[i] > nums2[st.top()]){if(umap.count(nums2[st.top()]) > 0 ){int index = umap[nums2[st.top()]];result[index] = nums2[i];}st.pop();}st.push(i);}return result;}
};

503. 下一个更大元素 II

503. 下一个更大元素 II - 力扣(LeetCode)

描述

给定一个循环数组 nums ( nums[nums.length - 1] 的下一个元素是 nums[0] ),返回 nums 中每个元素的 下一个更大元素 。

数字 x 的 下一个更大的元素 是按数组遍历顺序,这个数字之后的第一个比它更大的数,这意味着你应该循环地搜索它的下一个更大的数。如果不存在,则输出 -1 。

示例

示例 1:

输入: nums = [1,2,1]
输出: [2,-1,2]
解释: 第一个 1 的下一个更大的数是 2;
数字 2 找不到下一个更大的数;
第二个 1 的下一个最大的数需要循环搜索,结果也是 2。

示例 2:

输入: nums = [1,2,3,4,3]
输出: [2,3,4,-1,4]

提示

1 <= nums.length <= 104
-109 <= nums[i] <= 109

代码解析

和496 类似,为循环数组。将num数组扩充两倍连起来即可

class Solution {
public:vector<int> nextGreaterElements(vector<int>& nums) {vector<int> result(nums.size(),-1);vector<int> my_nums(nums.begin() , nums.end());stack<int> st;int indnx;// for(auto it:nums) my_nums.push_back(it); //循环插入my_nums.insert(my_nums.end(), nums.begin(), nums.end()); //insert插入st.push(0);for(int i=1 ; i<my_nums.size() ;i++){while(st.empty()==0 && my_nums[i] > my_nums[st.top()]){	//检测是否是第二圈if(st.top()>=nums.size()) indnx = st.top() - nums.size();else indnx = st.top();result[indnx] = my_nums[i];st.pop();}st.push(i);}return result;}
};

42. 接雨水

42. 接雨水 - 力扣(LeetCode)

描述

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

在这里插入图片描述

示例

示例 1:

输入: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 个单位的雨水(蓝色部分表示雨水)。

示例 2:

输入:height = [4,2,0,3,2,5]
输出:9

提示

n == height.length
1 <= n <= 2 * 104
0 <= height[i] <= 105

代码解析

单调栈

在这里插入图片描述
从栈头(元素从栈头弹出)到栈底的顺序应该是从小到大的顺序。

因为一旦发现添加的柱子高度大于栈头元素了,此时就出现凹槽了,栈头元素就是凹槽底部的柱子,栈头第二个元素就是凹槽左边的柱子,而添加的元素就是凹槽右边的柱子。
在这里插入图片描述
遇到相同的元素,更新栈内下标,就是将栈里元素(旧下标)弹出,将新元素(新下标)加入栈中。

例如 5 5 1 3 这种情况。如果添加第二个5的时候就应该将第一个5的下标弹出,把第二个5添加到栈中。

因为我们要求宽度的时候 如果遇到相同高度的柱子,需要使用最右边的柱子来计算宽度。
在这里插入图片描述

单调栈处理逻辑
  • 先将下标0的柱子加入到栈中

  • 然后开始从下标1开始遍历所有的柱子

  • 如果当前遍历的元素(柱子)高度小于栈顶元素的高度,就把这个元素加入栈中,因为栈里本来就要保持从小到大的顺序(从栈头到栈底)。

  • 如果当前遍历的元素(柱子)高度等于栈顶元素的高度,要跟更新栈顶元素,因为遇到相相同高度的柱子,需要使用最右边的柱子来计算宽度。

  • 如果当前遍历的元素(柱子)高度大于栈顶元素的高度,此时就出现凹槽了,如图所示:栈顶和栈顶的下一个元素以及要入栈的三个元素来接水!

  • 在这里插入图片描述

class Solution {
public:int trap(vector<int>& height) {if(height.size()<=2) return 0;stack<int> st;int result = 0;st.push(0);for(int i=1 ; i<height.size() ;i++){//当前柱子比栈顶的小if(height[i] < height[st.top()])st.push(i);//当前柱子和栈顶相等else if(height[i] == height[st.top()]){st.pop();st.push(i);//当前柱子比栈顶的大,产生了凹陷}else if(height[i] > height[st.top()]){while(st.empty()==0 && height[i] > height[st.top()]){int mid = st.top();st.pop();if(st.empty()==0) {int left = st.top();int right = i;int h = min(height[left] , height[right]) - height[mid];int w = right - left -1;result += h*w;}}st.push(i);}}return result;}
};

84. 柱状图中最大的矩形

84. 柱状图中最大的矩形 - 力扣(LeetCode)

描述

给定 n 个非负整数,用来表示柱状图中各个柱子的高度。每个柱子彼此相邻,且宽度为 1 。

求在该柱状图中,能够勾勒出来的矩形的最大面积。

示例

示例 1:

在这里插入图片描述

输入:heights = [2,1,5,6,2,3]
输出:10
解释:最大的矩形为图中红色区域,面积为 10

示例 2:

在这里插入图片描述

输入: heights = [2,4]
输出: 4

提示

1 <= heights.length <=105
0 <= heights[i] <= 104

代码解析

单调栈

我们可以遍历每根柱子,以当前柱子 i 的高度作为矩形的高,那么矩形的宽度边界即为向左找到第一个高度小于当前柱体 i 的柱体,向右找到第一个高度小于当前柱体 i 的柱体。

  • 和42接雨水类似
    为什么这么说呢,42. 接雨水 (opens new window)是找每个柱子左右两边第一个大于该柱子高度的柱子,而本题是找每个柱子左右两边第一个小于该柱子的柱子。

  • 那么因为本题是要找每个柱子左右两边第一个小于该柱子的柱子,所以从栈头(元素从栈头弹出)到栈底的顺序应该是从大到小的顺序!
    在这里插入图片描述

  • 只有栈里从大到小的顺序,才能保证栈顶元素找到左右两边第一个小于栈顶元素的柱子。

  • 所以本题单调栈的顺序正好与接雨水反过来。

  • 此时大家应该可以发现其实就是栈顶和栈顶的下一个元素以及要入栈的三个元素组成了我们要求最大面积的高度和宽度

class Solution {
public:int largestRectangleArea(vector<int>& heights) {heights.insert(heights.begin(), 0); // 数组头部加入元素0heights.push_back(0); // 数组尾部加入元素stack<int> st;int result = 0;st.push(0);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()==0 && heights[i] < heights[st.top()] ){int mid = st.top();st.pop();if(st.empty()==0){int left = st.top();int right = i;int sum = (right - left -1) * heights[mid];cout<<left<<' '<<mid<<' '<<right<<' '<<sum<<endl;if(sum > result) result = sum; }}st.push(i);   }}return result;}
};

这篇关于算法学习——LeetCode力扣单调栈篇的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

HarmonyOS学习(七)——UI(五)常用布局总结

自适应布局 1.1、线性布局(LinearLayout) 通过线性容器Row和Column实现线性布局。Column容器内的子组件按照垂直方向排列,Row组件中的子组件按照水平方向排列。 属性说明space通过space参数设置主轴上子组件的间距,达到各子组件在排列上的等间距效果alignItems设置子组件在交叉轴上的对齐方式,且在各类尺寸屏幕上表现一致,其中交叉轴为垂直时,取值为Vert

Ilya-AI分享的他在OpenAI学习到的15个提示工程技巧

Ilya(不是本人,claude AI)在社交媒体上分享了他在OpenAI学习到的15个Prompt撰写技巧。 以下是详细的内容: 提示精确化:在编写提示时,力求表达清晰准确。清楚地阐述任务需求和概念定义至关重要。例:不用"分析文本",而用"判断这段话的情感倾向:积极、消极还是中性"。 快速迭代:善于快速连续调整提示。熟练的提示工程师能够灵活地进行多轮优化。例:从"总结文章"到"用

哈希leetcode-1

目录 1前言 2.例题  2.1两数之和 2.2判断是否互为字符重排 2.3存在重复元素1 2.4存在重复元素2 2.5字母异位词分组 1前言 哈希表主要是适合于快速查找某个元素(O(1)) 当我们要频繁的查找某个元素,第一哈希表O(1),第二,二分O(log n) 一般可以分为语言自带的容器哈希和用数组模拟的简易哈希。 最简单的比如数组模拟字符存储,只要开26个c

不懂推荐算法也能设计推荐系统

本文以商业化应用推荐为例,告诉我们不懂推荐算法的产品,也能从产品侧出发, 设计出一款不错的推荐系统。 相信很多新手产品,看到算法二字,多是懵圈的。 什么排序算法、最短路径等都是相对传统的算法(注:传统是指科班出身的产品都会接触过)。但对于推荐算法,多数产品对着网上搜到的资源,都会无从下手。特别当某些推荐算法 和 “AI”扯上关系后,更是加大了理解的难度。 但,不了解推荐算法,就无法做推荐系

【前端学习】AntV G6-08 深入图形与图形分组、自定义节点、节点动画(下)

【课程链接】 AntV G6:深入图形与图形分组、自定义节点、节点动画(下)_哔哩哔哩_bilibili 本章十吾老师讲解了一个复杂的自定义节点中,应该怎样去计算和绘制图形,如何给一个图形制作不间断的动画,以及在鼠标事件之后产生动画。(有点难,需要好好理解) <!DOCTYPE html><html><head><meta charset="UTF-8"><title>06

学习hash总结

2014/1/29/   最近刚开始学hash,名字很陌生,但是hash的思想却很熟悉,以前早就做过此类的题,但是不知道这就是hash思想而已,说白了hash就是一个映射,往往灵活利用数组的下标来实现算法,hash的作用:1、判重;2、统计次数;

康拓展开(hash算法中会用到)

康拓展开是一个全排列到一个自然数的双射(也就是某个全排列与某个自然数一一对应) 公式: X=a[n]*(n-1)!+a[n-1]*(n-2)!+...+a[i]*(i-1)!+...+a[1]*0! 其中,a[i]为整数,并且0<=a[i]<i,1<=i<=n。(a[i]在不同应用中的含义不同); 典型应用: 计算当前排列在所有由小到大全排列中的顺序,也就是说求当前排列是第

csu 1446 Problem J Modified LCS (扩展欧几里得算法的简单应用)

这是一道扩展欧几里得算法的简单应用题,这题是在湖南多校训练赛中队友ac的一道题,在比赛之后请教了队友,然后自己把它a掉 这也是自己独自做扩展欧几里得算法的题目 题意:把题意转变下就变成了:求d1*x - d2*y = f2 - f1的解,很明显用exgcd来解 下面介绍一下exgcd的一些知识点:求ax + by = c的解 一、首先求ax + by = gcd(a,b)的解 这个

综合安防管理平台LntonAIServer视频监控汇聚抖动检测算法优势

LntonAIServer视频质量诊断功能中的抖动检测是一个专门针对视频稳定性进行分析的功能。抖动通常是指视频帧之间的不必要运动,这种运动可能是由于摄像机的移动、传输中的错误或编解码问题导致的。抖动检测对于确保视频内容的平滑性和观看体验至关重要。 优势 1. 提高图像质量 - 清晰度提升:减少抖动,提高图像的清晰度和细节表现力,使得监控画面更加真实可信。 - 细节增强:在低光条件下,抖

【数据结构】——原来排序算法搞懂这些就行,轻松拿捏

前言:快速排序的实现最重要的是找基准值,下面让我们来了解如何实现找基准值 基准值的注释:在快排的过程中,每一次我们要取一个元素作为枢纽值,以这个数字来将序列划分为两部分。 在此我们采用三数取中法,也就是取左端、中间、右端三个数,然后进行排序,将中间数作为枢纽值。 快速排序实现主框架: //快速排序 void QuickSort(int* arr, int left, int rig