[503.下一个更大元素II]
循环问题用 2*n , i % n 的方式
n = len(nums)
ans = [-1] * n
stack = []
for i in range(2 * n):
while len(stack) > 0 and nums[i % n] > nums[stack[-1]]:
ans[stack[-1]] = nums[i % n]
stack.pop()
stack.append(i % n)
return ans
[42. 接雨水]
1、双指针
注意点： 按列计算，找出左右的最大值
class Solution:
def trap(self, height: List[int]) -> int:
if len(height) <= 2:
return 0
n = len(height)
l_max_h, r_max_h = [0] * n, [0] * n
l_max_h[0], r_max_h[n-1] = height[0], height[n-1]
for i in range(1, n):
l_max_h[i] = max(height[i], l_max_h[i-1])
for j in range(n-2, -1, -1):
r_max_h[j] = max(height[j], r_max_h[j+1])
sum1 = 0
for k in range(1, n-1):
cur_h = min(l_max_h[k], r_max_h[k]) - height[k]
if cur_h > 0:
sum1 += cur_h
return sum1
2、单调栈
class Solution:
def trap(self, height: List[int]) -> int:
n = len(height)
# 单调递减栈
stack = []
ans = 0
for i in range(n):
while len(stack) > 0 and height[i] > height[stack[-1]]:
mid = stack.pop()
if len(stack) > 0:
h = min(height[stack[-1]], height[i]) - height[mid]
w = i - stack[-1] - 1
ans += h * w
stack.append(i)
return ans