代码随想录day48 || 739, 每日温度 496, 下一个更大元素 I 503, 下一个更大元素II

739 每日温度

func dailyTemperatures(temperatures []int) []int {
	// 双指针
	var res = make([]int, len(temperatures))

	for i:=0; i<len(temperatures); i++ {
		for j:=i+1; j<len(temperatures); j++ {
			if temperatures[j] > temperatures[i] {
				res[i] = j - i
				break
			}
		}
	}
	return res
}

// 时间n^2, 空间n  超时

//leetcode submit region begin(Prohibit modification and deletion)
func dailyTemperatures(temperatures []int) []int {
	// 单调栈
	if len(temperatures) == 1{
		return []int{0}
	}
	var res = make([]int, len(temperatures))
	var topidx int
	stack := list.New()

	for i:=0; i<len(temperatures); i++ {
		if stack.Len() == 0 {
			stack.PushFront(i)
			continue
		}
		topidx = stack.Front().Value.(int)
		if temperatures[i] <= temperatures[topidx] {
			stack.PushFront(i)
		}else {
			for temperatures[topidx] < temperatures[i]{
				idx := stack.Remove(stack.Front()).(int)
				res[idx] = i - idx
				if stack.Len() > 0 {
					topidx = stack.Front().Value.(int)
				}else {
					break
				}
			}
			stack.PushFront(i)
		}
	}
	return res
}

// 简洁版本
func dailyTemperatures(temperatures []int) []int {
	// 单调栈
	n := len(temperatures)
	res := make([]int, n)
	stack := []int{} // 使用切片作为栈

	for i := 0; i < n; i++ {
		for len(stack) > 0 && temperatures[i] > temperatures[stack[len(stack)-1]] {
			idx := stack[len(stack)-1]
			stack = stack[:len(stack)-1] // 弹出栈顶元素
			res[idx] = i - idx
		}
		stack = append(stack, i) // 压栈
	}

	return res
}

496 下一个更大元素

func nextGreaterElement(nums1 []int, nums2 []int) []int {
	// 两种思路，第一双循环暴力解法，第二可以单调栈求nums2每一个元素的更大元素，然后hash表nums1，得出结果
	var res = make([]int, len(nums1))
	var hash = make(map[int]int, len(nums1))

	for idx, num := range nums1 {
		hash[num] = idx
	}

	var stack = make([]int, len(nums2))
	var res2 = make([]int, len(nums2))
	for i:=0; i<len(nums2); i++{
		for len(stack) > 0 && nums2[i] > nums2[stack[0]] {
			idx := stack[0]
			stack = stack[1: ]
			res2[idx] = nums2[i]
		}
		stack = append([]int{i}, stack...)
	}
	//fmt.Println(res2)
	for i, v := range res2 {
		if idx, ok := hash[nums2[i]]; ok {
			if v == 0 {
				res[idx] = -1
			}else {
				res[idx] = v
			}
		}
	}
	return res
}

503 下一个更大元素II

func nextGreaterElements(nums []int) []int {
	// 思路取巧一下循环，将其变成两个数组叠加

	var newNums []int  // 两个数组
	newNums = append(newNums, nums...)
	newNums = append(newNums, nums...)
	fmt.Println(newNums)
	var stack = make([]int, len(newNums))
	var res = make([]int, len(newNums))
	for i, _ := range res {  // 初始化为-1
		res[i] = -1
	}


	for i:=0; i<len(newNums); i++{
		for len(stack) > 0 && newNums[i] > newNums[stack[len(stack) - 1]] {
			idx := stack[len(stack) - 1]
			stack = stack[ : len(stack) - 1]
			res[idx] = newNums[i]
		}
		stack = append(stack, i)
	}
	//fmt.Println(res)

	return res[ : len(nums)]
}

func nextGreaterElements(nums []int) []int {
	// 正常思路，涉及到环，通过取模运算实现正确的循环

	var stack = make([]int, len(nums))
	var res = make([]int, len(nums))
	for i, _ := range res {  // 初始化为-1
		res[i] = -1
	}

	length := len(nums)
	for i:=0; i<length * 2; i++{
		for len(stack) > 0 && nums[i % length] > nums[stack[len(stack) - 1]] {
			idx := stack[len(stack) - 1]
			stack = stack[ : len(stack) - 1]
			res[idx] = nums[i % length]
		}
		stack = append(stack, i % length)
	}
	//fmt.Println(res)

	return res
}