Leetcode 解题


LeetCode 第 739 题:根据每日气温列表,请重新生成一个列表,对应位置的输入是你需要再等待多久温度才会升高超过该日的天数。如果之后都不会升高,请在该位置用 0 来代替。
提示:气温列表 temperatures 长度的范围是 [1, 30000]。
示例:给定一个数组 T 代表了未来几天里每天的温度值,要求返回一个新的数组 D,D 中的每个元素表示需要经过多少天才能等来温度的升高。
给定 T: [23, 25, 21, 19, 22, 26, 23]
返回 D: [1, 4, 2, 1, 1, 0, 0]

739解题思路

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
func dailyTemperatures(T []int) []int {
	out := make([]int, len(T))
	var s Stack
	for i, v := range T {
		if i==0 {
			s = Stack{&ListNode739{v, 0, nil}, 1}
		} else if v<=s.Top.Val {
			s.Push(&ListNode739{v, i, nil})
		} else {
			for ; s.Length>0 && v>s.Top.Val; {
				t := s.Pop()
				out[t.Idx] = i - t.Idx
			}
			s.Push(&ListNode739{v, i, nil})
		}
	}
	return out
}

type ListNode739 struct {
	Val  int
	Idx  int
	Next *ListNode739
}

type Stack struct {
	Top    *ListNode739
	Length int
}

func (s *Stack) Push(n *ListNode739) {
	n.Next = s.Top
	s.Top = n
	s.Length++
}

func (s *Stack) Pop() *ListNode739 {
	s.Length--
	oldTop := s.Top
	s.Top = s.Top.Next
	return oldTop
}
comments powered by Disqus
Using Hugo & Soda theme
fc4soda ❤ 2018.04.24~