day 51 |● 503.下一个更大元素II ● 42. 接雨水

503.下一个更大元素II

显示的是循环链表，所以需要遍历两遍。
用i%len(nums)保证循环两遍即可。

func nextGreaterElements(nums []int) []int {
    res := make([]int, len(nums))
    for i := 0; i < len(nums); i++{
        res[i] = -1
    }

    stack := make([]int, 0)
    stack = append(stack,0)
    for i := 1; i % len(nums) < len(nums); i++{
        if i == 2 * len(nums){
            break
        }
        if nums[i % len(nums)] > nums[stack[len(stack) - 1]]{
            for len(stack) != 0 && nums[i % len(nums)] > nums[stack[len(stack) - 1]]{
                res[stack[len(stack) - 1]] = nums[i % len(nums)]
                stack = stack[:len(stack) - 1]
            }

            if i < len(nums){
                stack = append(stack, i)
            }
        }else{
            if i < len(nums){
                stack = append(stack, i)
            }
        }
    } 
    return res
}
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

42. 接雨水

第一种方法是双指针法，记录包括该点在内左面和右边的最大值，然后累加的过程中挑选小的哪一个作为接雨水的边。这样做可以看成按列来做，每次操作的宽度均为1.

第二种方法是单调栈解决，如果当前值大于栈顶元素，说明肯定是由了凹坑，所以进行雨水的计算。这个就是按照行来计算了。同时在for循环中要进行判定是否是最边上一个。

func trap(height []int) int {
    maxleft := make([]int, len(height))
    maxleft[0] = height[0]
    for i := 1; i < len(height); i++{
        maxleft[i] = max(maxleft[i - 1], height[i])
    }
    maxright := make([]int, len(height))
    maxright[len(height) - 1] = height[len(height) - 1]
    for i := len(height) - 2; i >= 0; i--{
        maxright[i] = max(height[i], maxright[i+1])
    }
    res := 0
    for i := 1; i < len(height) - 1; i++{
        tmp := min(maxleft[i], maxright[i]) - height[i]
        res += tmp
    }
    return res
}
func max(a, b int)int{
    if a < b{
        return b
    }
    return a
}
func min(a, b int)int{
    if a < b{
        return a 
    }
    return b
}
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

func trap(height []int) int {
    stack := make([]int, 0)
    stack = append(stack, 0)
    res := 0
    for i := 1; i < len(height); i++{
        if height[i] > height[stack[len(stack) - 1]]{
            for len(stack) != 0 && height[i] > height[stack[len(stack) - 1]]{
                bottom := stack[len(stack) - 1]
                stack = stack[:len(stack) - 1]
                if len(stack) != 0{
                    h := min(height[stack[len(stack) - 1]], height[i]) - height[bottom]
                    w := i - stack[len(stack) - 1] - 1
                    res += h * w
                }
            }
            stack = append(stack,i)
        }else if height[i] == height[stack[len(stack) - 1]]{
            stack = stack[:len(stack) - 1]
            stack = append(stack,i)
        }else{
            stack = append(stack,i)
        }
    }
    return res
}

func min(a, b int)int{
    if a < b{
        return a 
    }
    return b
}
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