注：Day58是休息日。
本文目录
503.下一个更大元素II
代码随想录：503.下一个更大元素II
Leetcode：503.下一个更大元素II
做题
和之前的739. 每日温度一样，只不过可以循环，我这边是多遍历一次nums。
class Solution:
def nextGreaterElements(self, nums: List[int]) -> List[int]:
stack = []
res = [-1] * len(nums)
for j in range(2):
for i in range(len(nums)):
while stack and nums[i] > nums[stack[-1]]:
if res[stack[-1]] == -1:
res[stack[-1]] = nums[i]
stack.pop()
stack.append(i)
return res
时间复杂度: O(n)
空间复杂度: O(n)
看文章
思路一致，只是实现上有细微差别。
42. 接雨水
代码随想录：42. 接雨水
Leetcode：42. 接雨水
做题
之前面试做过这道题，处理得比较复杂，这里学学新思路。
看文章
维持一个非严格单调递减的栈，当遍历到新元素大于栈顶元素时，开始计算。雨水高度 = min(凹槽左侧高度, 凹槽右侧高度) - 凹槽底部高度，雨水宽度 = 凹槽右侧的下标 - 凹槽左侧的下标 - 1。
# 单调栈压缩版
class Solution:
def trap(self, height: List[int]) -> int:
stack = [0]
result = 0
for i in range(1, len(height)):
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
以往忽略的知识点小结
- 之前做 42. 接雨水 应该是用暴力求解+优化，现在要学一学单调栈的做法
个人体会
完成时间：1h20min。
心得：题相对简单，主要是学会 42. 接雨水 的单调栈做法。
标签：nums,Python,随想录,42,雨水,height,凹槽,stack From： https://blog.csdn.net/Xiu_Yuan123/article/details/139400023