首页 > 其他分享 >单调栈

单调栈

时间:2023-03-04 20:35:49浏览次数:40  
标签:逻辑 倒序 元素 单调 递减 解法

一但要求下一个更大的元素,就是用单调栈解,力扣题库相似的题目都是这个解法。

栈(stack)是很简单的一种数据结构,先进后出的逻辑顺序,符合某些问题的特点,比如说函数调用栈。

单调栈实际上就是栈,只是利用了一些巧妙的逻辑,使得每次新元素入栈后,栈内的元素都保持有序(单调递增或单调递减)。

 

例题:

496. 下一个更大元素 I

解法:单调栈 + 哈希表

 

 第1个子问题用单调栈解决。倒序遍历nums2​,并用单调栈中维护当前位置右边的更大的元素列表,从栈底到栈顶的元素是单调递减的。

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

标签:逻辑,倒序,元素,单调,递减,解法
From: https://www.cnblogs.com/spacerunnerZ/p/17179022.html

相关文章

  • 字节青训营主题发文——单调栈
    主题说明现有n个宽度为1的柱子,给出n个非负整数依次表示柱子的高度,排列后如下图所示,此时均匀从上空向下撒青豆,计算按此排列的柱子能接住多少青豆。(不考虑边角堆积)......
  • 最大子序和——单调队列+DP
    输入一个长度为n的整数序列,从中找出一段长度不超过m的连续子序列,使得子序列中所有数的和最大。注意:子序列的长度至少是1。输入格式第一行输入两个整数n,m。第二......
  • P5788 【模板】单调栈
    P5788【模板】单调栈【模板】单调栈题目背景模板题,无背景。2019.12.12更新数据,放宽时限,现在不再卡常了。题目描述给出项数为n的整数数列a_{1...n}。定义函数......
  • acwing 单调栈
    原题给定一个长度为N的整数数列,输出每个数左边第一个比它小的数,如果不存在则输出-1。输入格式第一行包含整数N,表示数列长度。第二行包含N个整数,表示整数数列。......
  • 刷刷刷 Day 37 | 738. 单调递增的数字
    738.单调递增的数字LeetCode题目要求当且仅当每个相邻位数上的数字 x 和 y 满足 x<=y 时,我们称这个整数是单调递增的。给定一个整数n,返回小于或等于n的最......
  • 代码随想录算法训练营第三十六天 | 738.单调递增的数字,714. 买卖股票的最佳时机含手续
    Day36周日休息~一、参考资料单调递增的数字https://programmercarl.com/0738.%E5%8D%95%E8%B0%83%E9%80%92%E5%A2%9E%E7%9A%84%E6%95%B0%E5%AD%97.html买卖股票的......
  • 单调栈
    单调栈给定一个长度为N的整数数列,输出每个数左边第一个比它小的数,如果不存在则输出−1。输入格式第一行包含整数N,表示数列长度。第二行包含N个整数,表示整数数列......
  • 浅谈单调队列解决滑动窗口问题
    这次我们了解一下滑动窗口的问题首先,让我们了解一下滑动窗口是什么?这里有一张图(来自POJ),解释了滑动窗口的意思:我们可以看见,一个长度固定为3的框(窗口)从左端点移动到右......
  • 单调栈
    栈是一种后进先出的线性的数据结构,但若在栈的结构之上再规定栈中元素大小需满足单调关系,即成为单调栈。单调栈分为单调递增栈和单调递减栈:1.单调递增栈即栈内元素保持单......
  • 单调队列
    单调队列是什么呢?可以直接从问题开始来展开。Poj2823给定一个数列,从左至右输出每个长度为m的数列段内的最小数和最大数。数列长度:N<=106,m<=N暴力解很直观的一种解法,那就......