您现在的位置是:首页 >学无止境 >代码随想录算法训练营第五十九天| 503.下一个更大元素II、42. 接雨水网站首页学无止境

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

神楽七奈世界第一可爱 2023-06-28 16:00:02
简介代码随想录算法训练营第五十九天| 503.下一个更大元素II、42. 接雨水

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

503.下一个更大元素II

题目

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]

来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/next-greater-element-ii
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

代码

class Solution:
    def nextGreaterElements(self, nums: List[int]) -> List[int]:
        result=[-1]*(len(nums))
        stack=[0]
        for i in range(1,len(nums)*2):
            if nums[i%len(nums)]<=nums[stack[-1]]:
                stack.append(i%len(nums))
            else:
                while len(stack)!=0 and nums[i%len(nums)]>nums[stack[-1]]:
                    result[stack[-1]]=nums[i%len(nums)]
                    stack.pop()
                stack.append(i%len(nums))
        return result

42. 接雨水

题目

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

来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/trapping-rain-water
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

代码

class Solution:
    def trap(self, height: List[int]) -> int:
        result=0
        stack=[0]
        for i in range(1,len(height)):
            if height[i]<=height[stack[-1]]:
                stack.append(i)
            else:
                while stack and height[i] > height[stack[-1]]:
                    mid_height = stack.pop()
                    if stack:
                    # 雨水高度是 min(凹槽左侧高度, 凹槽右侧高度) - 凹槽底部高度
                        h = min(height[stack[-1]], height[i]) - height[mid_height]
                    # 雨水宽度是 凹槽右侧的下标 - 凹槽左侧的下标 - 1
                        w = i - stack[-1] - 1
                    # 累计总雨水体积
                        result += h * w
                stack.append(i)
        return result
风语者!平时喜欢研究各种技术,目前在从事后端开发工作,热爱生活、热爱工作。