单调栈

🍎 题目汇总

496. 下一个更大元素 I

503. 下一个更大元素 II(用栈来存储下标)

556. 下一个更大元素 III


🍎 具体分析

496. 下一个更大元素 I

1)问题描述

下一个更大元素问题描述

2)分析

建立nums2各个元素和位于后面最近的更大元素的键值关系(若不存在,则赋值为-1)(通过哈希表和栈来实现找下一个更大元素)

3)代码实现

下一个更大元素代码实现

✨注意:这里栈存储的元素结果是一个不升的数组,并且是从nums2的后面开始遍历,意义在于,进栈出栈都是从最后开始,在比较过程中,找到了最靠近nums2[i]的且位于nums2[i]后面的元素。

556. 下一个更大元素 III

1)问题描述

下一个更大元素iii


2)分析

(1)数字转字符串sprintf(str, "%d",number)

(2)利用栈,从后往前遍历,其结果是一个不降的数组

(3)从后面开始遍历字符串,当出现当前元素temp<栈顶元素时(也是当前元素后面的元素),栈顶元素先用idx标定起来,然后让它出栈。循环这个操作,直到temp>=栈顶元素,这时候标定的idx的元素就是和temp交换且能使数组从后到temp位置保持单调性的正确对象。

(4)在temp元素后一个位置到最后进行一个逆序排列,即为结果。

(5)把字符串转换为整数。(✨注意:由于要考虑溢出问题,因此可以首先标定res为long long,把转换结果赋值给res,判断res是否溢出,若是溢出,则为-1,否则强制类型转换(int)。由于用到这项操作,因此不能用atoi()函数【把字符串转换为整数】,因为atoi()直接返回int函数,当出现溢出时会报错)

3)代码实现

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
【社区内容提示】社区部分内容疑似由AI辅助生成,浏览时请结合常识与多方信息审慎甄别。
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

相关阅读更多精彩内容

友情链接更多精彩内容