文档讲解：代码随想录
视频讲解：代码随想录B站账号
状态：看了视频题解和文章解析后做出来了
503.下一个更大元素II
class Solution:
def nextGreaterElements(self, nums: List[int]) -> List[int]:
res = [-1] * len(nums)
stack = []
for i in range(len(nums)*2):
while len(stack) > 0 and nums[i%len(nums)] > nums[stack[-1]]:
res[stack[-1]] = nums[i%len(nums)]
stack.pop()
stack.append(i%len(nums))
return res- 时间复杂度：O(n)
- 空间复杂度：O(n)
这道题和每日温度非常相似，只不过这次的数组是头接尾的，也就是说后面的元素也可以视前面的元素为比自己大的元素。
第一种方法是复制一个nums数组然后和原数组拼接在一起，最后把res resize成原来的大小，虽然最后的resize复杂度为O(1)，但扩充数组的复杂度就是O(n)了，不太值得。
比较好的一种方式是循环这个数组两遍，所以在for循环的range里，使用的是len(nums) * 2。
在提取当前元素的值时，需要用到取模操作，取nums的长度，也就是说假设nums长度为5，那么循环到6的时候，下标为1。这个取模操作要应用到所有和 i 相关的操作中防止逾越index问题。
42. 接雨水
暴力双指针
class Solution:
def trap(self, height: List[int]) -> int:
res = 0
for i in range(1, len(height)-1):
left_bar, right_bar = height[i], height[i]
for j in range(i+1, len(height)):
if height[j] > right_bar:
right_bar = height[j]
for z in range(i-1, -1, -1):
if height[z] > left_bar:
left_bar = height[z]
h = min(right_bar, left_bar) - height[i]
res += h
return res- 时间复杂度：O(n^2)
- 空间复杂度：O(n)
可以从行和列接雨水，从列接雨水的逻辑比较清晰，因为宽度一定是1所以只需要计算高度就行了。
想要计算一列能够接多少雨水，和木桶问题很像，取决于两边较矮的那个边的长度。
所以对于每一列，只需要首先将left_bar，right_bar初始化为当前的高度，然后依次向左和向右遍历，只要找到比左bar和右bar更高的bar就更新。
最后计算的时候，取两者的较小然后减去当前的高度 h = min(right_bar, left_bar) - height[i]。
卡哥的代码里最后还加了个判断h大于0的if，这个没必要哈因为left_bar和right_bar只有比height[i]大的时候才更新，没找到就是它自己，所以最差情况也是0，不可能小于0。
双指针优化
class Solution:
def trap(self, height):
if len(height) <= 2:
return 0
size = len(height)
max_left = [0] * size
max_right = [0] * size
# Record the maximum height to the left of each bar
max_left[0] = height[0]
for i in range(1, size):
max_left[i] = max(height[i], max_left[i - 1])
# Record the maximum height to the right of each bar
max_right[size - 1] = height[size - 1]
for i in range(size - 2, -1, -1):
max_right[i] = max(height[i], max_right[i + 1])
# Calculate the total trapped water
total_water = 0
for i in range(size):
water_at_bar = min(max_left[i], max_right[i]) - height[i]
total_water += water_at_bar
return total_water
- 时间复杂度：O(n)
- 空间复杂度：O(n)
在暴力方法中，我们每到一个位置都要计算它左边和右边的最高bar，这里就会涉及很多重复计算。如果我们把每个点的左右最高bar首先计算出来保存在两个数组中，在循环过程中使用这个数组中的值就避免了重复运算。
单调栈
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- 时间复杂度：O(n)
- 空间复杂度：O(n)
首先明确单调栈是按行来接雨水的：
然后确定单调栈是递增还是递减，这道题中是从栈头到栈尾单调递增。因为如果遇到了比前一个高的元素，说明遇到了桶的右bar，这时候就要pop来进行操作了。
分三种情况：
1. 如果当前元素小于前一个元素，直接入栈并保持单调递增。
2. 如果当前元素等于前一个元素，5543的情况，我们在后续计算雨水体积的时候，肯定也是用右侧的两个5的第二个5来计算，所以先pop再append。
3. 如果当前元素大于前一个元素，开始操作了。
- 首先pop获取上一个元素的高度，赋值给mid变量
- 计算高度，高度为当前元素 i 和当前栈头，也就是 i - 2的高度的较小值
- 计算宽度，宽度就是当前元素下标 i 减去栈头，再加1。假设当前元素下标为5，栈头为3，那么
5 - 3 - 1 = 1，宽度也只是1，符合题意。
- 将长乘以宽的体积计入结果变量res中。
