day50| ● 739. 每日温度 ● 496.下一个更大元素 I

739. 每日温度

到了单调栈的环节，要寻找任一个元素的右边或者左边第一个比自己大或者小的元素的位置，此时我们就要想到可以用单调栈了。时间复杂度为O(n)。
如果求一个元素右边第一个更大元素，单调栈就是递增的（从栈头到栈底），如果求一个元素右边第一个更小元素，单调栈就是递减的。
而且还不要忘记，当判断完当前的后，要把当前i也压到栈里。

func dailyTemperatures(temperatures []int) []int {
    res := make([]int, len(temperatures))
    stack := make([]int, 0)
    stack = append(stack, 0)
    for i := 1; i < len(temperatures); i++{
        if temperatures[i] > temperatures[stack[len(stack) - 1]]{
            for len(stack) != 0 && temperatures[i] > temperatures[stack[len(stack) - 1]]{
                res[stack[len(stack) - 1]] = i - stack[len(stack) - 1]
                stack = stack[:len(stack) - 1]
            }
            stack = append(stack, i)
        }else{
            stack = append(stack, i)
        } 
    }
    return res
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

496.下一个更大元素 I

首先还是单调栈的思想，但是由于是两个数组，所以需要用hash建立映射。

func nextGreaterElement(nums1 []int, nums2 []int) []int {
    hash := make(map[int]int)
    for i := 0; i < len(nums1); i++{
        hash[nums1[i]] = i
    }

    stack := make([]int, 0)
    stack = append(stack,0)
    tmp := make([]int, len(nums1))
    for i := 0; i < len(tmp); i++{
        tmp[i] = -1
    }
    for i := 1; i < len(nums2);i++{
        if nums2[i] > nums2[stack[len(stack) - 1]]{
            for len(stack) != 0 && nums2[i] > nums2[stack[len(stack) - 1]]{
                if v, ok := hash[nums2[stack[len(stack) - 1]]];ok{
                    tmp[v] = nums2[i]
                }
                stack = stack[:len(stack) - 1]
            }
            stack = append(stack, i)
        }else{
            stack = append(stack, i)
        }
    }
    return tmp
}
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