代码随想录算法训练营第59天|● 503.下一个更大元素II ● 42. 接雨水

503. 下一个更大元素 II

中等
相关标签
相关企业
给定一个循环数组 nums （ nums[nums.length - 1] 的下一个元素是 nums[0] ），返回 nums 中每个元素的 下一个更大元素 。
数字 x 的 下一个更大的元素 是按数组遍历顺序，这个数字之后的第一个比它更大的数，这意味着你应该循环地搜索它的下一个更大的数。如果不存在，则输出 -1 。

示例 1:
输入: nums = [1,2,1]
输出: [2,-1,2]
解释: 第一个 1 的下一个更大的数是 2；
数字 2 找不到下一个更大的数；
第二个 1 的下一个最大的数需要循环搜索，结果也是 2。
示例 2:
输入: nums = [1,2,3,4,3]
输出: [2,3,4,-1,4]

提示:

• 1 <= nums.length <= 10(4)
• -10(9) <= nums[i] <= 10(9)

代码

func nextGreaterElements(nums []int) []int {
    /*
        复制初始数组，遍历[i,n+i]
    */
    n := len(nums)
    nums = append(nums, nums...)
    res := make([]int, 2*n)
    stack := make([]int, 0)
    for i := 0; i < 2*n; i++ {
        res[i]=-1
    }
    for i := 0; i < 2*n; i++ {
        if len(stack) != 0 {
            for len(stack) != 0 && nums[stack[len(stack)-1]] < nums[i] {
                j := stack[len(stack)-1]
                res[j] = nums[i]
                stack = stack[:len(stack)-1]
            }
        }
        stack = append(stack, i)
    }
    return res[:n]
}

42. 接雨水

困难
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

示例 1：
输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
输出：6
解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。
示例 2：
输入：height = [4,2,0,3,2,5]
输出：9

提示：

• n == height.length
• 1 <= n <= 2 * 10(4)
• 0 <= height[i] <= 10(5)

思路

• 递减储存
• res是分层累加的结果

代码

func trap(height []int) int {
    n := len(height)
    l, r := make([]int, n), make([]int, n)
    /*
        两边找max
    */
    l[0] = height[0]
    for i := 1; i < n; i++ {
        l[i] = max(l[i-1], height[i])
    }
    r[n-1] = height[n-1]
    for i := n - 2; i >= 0; i-- {
        r[i] = max(r[i+1], height[i])
    }
    res := 0
    for i := 0; i < n; i++ {
        res += min(r[i], l[i]) - height[i]
    }
    return res
}