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

503. 下一个更大元素 II

还是比较容易想的，扩展数组一倍即可。

class Solution:def nextGreaterElements(self, nums: List[int]) -> List[int]:extended_nums = nums * 2n = len(nums)mono = []res = [- 1] * nfor i, num in enumerate(extended_nums):while mono and extended_nums[mono[-1]] < num:if mono[-1] < n:res[mono[-1]] = nummono.pop()mono.append(i)return res

看了代码随想录的题解可以用%运算减少空间复杂度。

class Solution:def nextGreaterElements(self, nums: List[int]) -> List[int]:n = len(nums)mono = []res = [- 1] * nfor i in range(2 * n):while mono and nums[mono[-1]] < nums[i % n]:res[mono[-1]] = nums[i % n]mono.pop()mono.append(i % n)return res

42. 接雨水

手撕成功！

维护单调栈找右边第一个大的就是右边界，这时候把当前元素pop出来，如果栈不为空，说明左边也有比当前元素大的左边界，那么这俩边界之间就可以接雨水！！！

class Solution:def trap(self, height: List[int]) -> int:res = 0mono = []for right in range(len(height)):while mono and height[mono[-1]] < height[right]:cur = mono.pop()if mono:left = mono[-1]res += (right - left - 1) * (min(height[left], height[right]) - height[cur])mono.append(right)return res

信心巨大增强！！！

记录一下双指针暴力解法：

class Solution:def trap(self, height: List[int]) -> int:n = len(height)if n == 0:return 0ans = 0for i in range(1, n - 1):  # 对于每个位置max_left = max(height[:i])  # 找到左边的最大值max_right = max(height[i+1:])  # 找到右边的最大值# 计算当前位置能接的雨水量water = min(max_left, max_right) - height[i]if water > 0:ans += waterreturn ans

动态规划解法：

class Solution:def trap(self, height: List[int]) -> int:n = len(height)left_max = [0] * nright_max = [0] * nans = 0# 从左向右计算左侧最大高度left_max[0] = height[0]for i in range(1, n):left_max[i] = max(left_max[i - 1], height[i])# 从右向左计算右侧最大高度right_max[n - 1] = height[n - 1]for i in range(n - 2, -1, -1):right_max[i] = max(right_max[i + 1], height[i])# 计算每个位置能接的雨水量，并累加for i in range(n):ans += min(left_max[i], right_max[i]) - height[i]return ans

双指针究极优化：

class Solution:def trap(self, height: List[int]) -> int:left, right = 0, len(height) - 1  # 初始化左右指针left_max, right_max = height[left], height[right]  # 初始化左右最大值ans = 0while left < right:# 更新左侧最大值和右侧最大值left_max = max(left_max, height[left])right_max = max(right_max, height[right])# 根据当前的最大值，计算能接的雨水，并移动指针if left_max < right_max:ans += left_max - height[left]left += 1else:ans += right_max - height[right]right -= 1return ans

今日总结：

接雨水一刷AC，虽然花了1小时，成就感满满。