原题与翻译

Given a list of daily temperatures, produce a list that, for each day in the input, tells you how many days you would have to wait until a warmer temperature. If there is no future day for which this is possible, put 0 instead.
提供一份温度报表, 对于每一天的温度, 都需要你计算出还要等待多久才会出现更热的气温. 如果报表中未来时间内没有更高气温,则,返回 0.
For example, given the list temperatures = [73, 74, 75, 71, 69, 72, 76, 73], your output should be [1, 1, 4, 2, 1, 1, 0, 0].

比如,对于这份气温报表: [73, 74, 75, 71, 69, 72, 76, 73]

你应当返回 :[1, 1, 4, 2, 1, 1, 0, 0]

Note: The length of temperatures will be in the range [1, 30000]. Each temperature will be an integer in the range [30, 100].

注意: 气温报表时间范围在 [1, 30000] 之内. 每一个温度都是在 [30, 100] 范围内的整数.

思路

一 暴力法(超时)

堆栈方法

基本思路,

初始化: 用堆栈 temperaturesSize 存储当日气温, 初始堆栈为空, 默认将第一天的气温压栈(压栈的其实是’第一天’,而不是第一天的气温). 用向量 result 存储结果, 初始化长度为气温报表长度, 默认值为零.

循环: 若栈顶那日的温度高于后一日, 弹栈, 并将后一日压栈, 这两日的时间间距, 就是更高温度出现时,’那日’ 需要等待的时间; 若栈顶那日温度低于(或等于)后一日, 不弹栈, 将后一日压栈, 尔后遍历再后一日. 往复弹出栈顶元素, 直到遍历完整张气温报表.

细节: 遍历完成后, 任有未弹栈的元素, 即说明此元素之后没有温度更高的日期, 故无法弹栈. 此时, 这一天的更高温期待时间为默认值 0.

Hello world!
文章已创建 211

发表评论

电子邮件地址不会被公开。 必填项已用*标注

相关文章

开始在上面输入您的搜索词,然后按回车进行搜索。按ESC取消。

返回顶部