[代码随想录]Day51-单调栈part02-526互联

题目：503. 下一个更大元素 II

思路：

总之就是走两次nums，可以拼接，也可以用下面的取余方式。

代码：

func nextGreaterElements(nums []int) []int {
    lens := len(nums)
    res := make([]int, lens)
    for i := 0; i < lens; i++{
        res[i] = -1
    }
    stack := make([]int,0)
    for i:=0; i < lens * 2; i++ {
        for len(stack) > 0 && nums[i%lens] > nums[stack[len(stack)-1]] {
            index := stack[len(stack) - 1]
            stack = stack[:len(stack)-1]
            res[index] = nums[i%lens]
        }
        stack = append(stack, i%lens)
    }
    return res
}

参考：

代码随想录

题目：42. 接雨水

思路：

这个双指针容易想也容易做，找到一个位置左右最高点，然后选其中小的一个减去当前位置高度就是蓄水能力(负数就去掉)。

代码1：

双指针法

func trap(height []int) int {
    lens := len(height)
    lh := make([]int, lens)
    rh := make([]int, lens)
    lh[0] = height[0]
    rh[lens-1]= height[lens-1]
    res := 0
    for i:=1; i<lens;i++ {
        lh[i] = max(lh[i-1],height[i])
    }
    for i := lens-2; i>=0;i-- {
        rh[i] = max(rh[i+1], height[i])
    }
    for i:=1;i<=lens-2;i++ {
        h := min(rh[i], lh[i]) - height[i]
        if h > 0 {
            res += h
        }
    }
    return res
}
func max(a,b int)int{
    if a>b{
        return a
    }
    return b
}
func min(a,b int)int{
    if a<b{
        return a
    }
    return b
}

参考：