739.M 每日温度

Problem: 739. 每日温度

思路

思路1：暴力解法。

核心思路是对于每个元素，需要在右侧找到更高温度的最小下标。因此考虑用next数组表示某个温度的第一次出现的位置，从右往左遍历输入数组，分别遍历[当前温度+1,100]这个区间，看最小的下标是哪个，即为当前位置的解。

每次处理完一个元素后，都把当前元素的温度和下标存入next数组。

该解法时间复杂度为O(n*m), n为输入数组长度，m为常数100，所以时间复杂度近似于O(n)

---

思路2：单调栈。

维护一个元素单调递减的栈：

• 如果栈不为空，而且当前元素大于栈顶元素：

  • 那么说明找到了栈顶元素的解，设置到ans数组，然后把栈顶元素出栈。

• 否则，当前元素入栈

Code

代码1：

func dailyTemperatures(temperatures []int) []int {
	ans := make([]int, len(temperatures))
	next := make([]int, 101)
	for i := range next {
		next[i] = math.MaxInt32
	}
	for i := len(temperatures) - 1; i >= 0; i-- {
		smallestWarmerIndex := math.MaxInt32
		for temp := temperatures[i] + 1; temp <= 100; temp++ {
			if smallestWarmerIndex > next[temp] {
				smallestWarmerIndex = next[temp]
			}
		}

		if smallestWarmerIndex != math.MaxInt32 {
			ans[i] = smallestWarmerIndex - i
		}

		next[temperatures[i]] = i
	}

	return ans
}

代码2：

func dailyTemperatures(temperatures []int) []int {
	ans := make([]int, len(temperatures))
	var stack []int
	for i, temp := range temperatures {
		// 当前元素大于栈顶元素
		for len(stack) > 0 && temp > temperatures[stack[len(stack)-1]] {
			// 找到栈顶元素的解
			ans[stack[len(stack)-1]] = i - stack[len(stack)-1]
			// 栈顶元素出栈
			stack = stack[:len(stack)-1]
		}
		stack = append(stack, i)
	}

	return ans
}