手机网站建设实验报告,小程序商城开发北京,wordpress开发ide,企业网站建设市场报价应用情景
求当前元素 前面/后面#xff0c;第一个比它 小/大 的元素的 值/下标/下标距离
优点
剔除重复寻路操作#xff0c;将暴力 O(n^2) 优化到 O(n)
性质
从栈底开始#xff0c;元素 单调递增/单调递减
单调性视具体情景而定 (找较大值还是较小值、找的方向)
思路…应用情景
求当前元素 前面/后面第一个比它 小/大 的元素的 值/下标/下标距离
优点
剔除重复寻路操作将暴力 O(n^2) 优化到 O(n)
性质
从栈底开始元素 单调递增/单调递减
单调性视具体情景而定 (找较大值还是较小值、找的方向)
思路
以某种形式存放遍历过的元素使该种存放形式符合情景要求
讨论当前元素与栈顶元素比较大小后的几种情况分别对应什么操作
实现
按遍历顺序生成结果
1.存放每一个遍历过的元素 (写在循环体最后)
2.对于当前元素要知道有没有比它 大/小 的就从栈顶向下找不满足条件的直接出栈
因为对于之后还没遍历到的元素栈顶不满足条件的元素和当前元素相比
一定劣于当前元素不会再用到了
3.经历过 2. 之后当前栈一定符合条件若栈为空则没有元素比当前元素更 小/大
若栈非空则栈顶元素一定是第一个比当前元素 小/大 的
按其他顺序生成结果略 (我遇到的题目都是按遍历顺序生成结果更优)
注意事项
注意讨论遍历方向有时反着遍历思路和代码更简洁
栈中元素有时候需要存数值有时候要存下标视题目要求而定
例题
LeetCode.739.每日温度
题目与题解
题解 力扣 LeetCode 739 每日温度 C-CSDN博客https://blog.csdn.net/qwq_ovo_pwp/article/details/143243618?spm1001.2014.3001.5501
