739. 每日温度
请根据每日 气温 列表,重新生成一个列表。对应位置的输出为:要想观测到更高的气温,至少需要等待的天数。如果气温在这之后都不会升高,请在该位置用 0 来代替。
思路:
通常一维数组,要寻找任一个元素的右边或者左边第一个比自己大或者小的元素的位置,此时我们就要想到可以用单调栈了。时间复杂度为O(n)。
本题使用一个从栈底到栈顶递减的单调栈,while新元素 i 比栈顶的元素大,那就弹出栈顶元素x,那元素x距离第一个比自己大的元素就是 i-x.
496.下一个更大元素 I
给你两个 没有重复元素 的数组 nums1 和 nums2 ,其中nums1 是 nums2 的子集。请你找出 nums1 中每个元素在 nums2 中的下一个比其大的值。nums1 中数字 x 的下一个更大元素是指 x 在 nums2 中对应位置的右边的第一个比 x 大的元素。如果不存在,对应位置输出 -1 。
思路:
和上一题几乎一模一样,就不过把元素放到了nums1而已。
以下是卡哥资料
739. 每日温度
今天正式开始单调栈,这是单调栈一篇扫盲题目,也是经典题。
大家可以读题,思考暴力的解法,然后在看单调栈的解法。 就能感受出单调栈的巧妙
https://programmercarl.com/0739.%E6%AF%8F%E6%97%A5%E6%B8%A9%E5%BA%A6.html
496.下一个更大元素 I
本题和 739. 每日温度 看似差不多,其实 有加了点难度。