您现在的位置是:首页 >技术教程 >代码随想录算法训练营第五十九天网站首页技术教程
代码随想录算法训练营第五十九天
简介代码随想录算法训练营第五十九天
代码随想录算法训练营第五十九天| 503.下一个更大元素II,42. 接雨水
503.下一个更大元素II
题目链接:下一个更大元素II
因为可以循环,直接拼一个nums在nums后面就行了。
class Solution:
def nextGreaterElements(self, nums: List[int]) -> List[int]:
nums1 = nums + nums
res = [-1] * len(nums1)
stack = [0]
for i in range(1,len(nums1)):
if nums1[i] <= nums1[stack[-1]]:
stack.append(i)
else:
while stack and nums1[i] > nums1[stack[-1]]:
res[stack[-1]] = nums1[i]
stack.pop()
stack.append(i)
#print(res)
return res[:len(nums)]
42. 接雨水
题目链接:接雨水
这种题还得画图找规律。
复杂单调栈
这里我找到的规律是如果有坑(左右更大都存在),就把这块面积收集了,但是还是不太会处理平坡(上半张图的两个3,7),不能加两次但也不能直接跳过,因为下面还有一个坑。
class Solution:
def trap(self, height: List[int]) -> int:
hl = [-1]*len(height)
hr = [-1]*len(height)
stack = [0]
stack2 = [len(height)-1]
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]]:
hl[stack[-1]] = i
stack.pop()
stack.append(i)
for i in range((len(height)-2),-1,-1):
if height[i] <= height[stack2[-1]]:
stack2.append(i)
else:
while stack2 and height[i] > height[stack2[-1]]:
hr[stack2[-1]] = i
stack2.pop()
stack2.append(i)
i = 0
res = 0
hole = []
while i < len(height):
if hl[i] != -1 and hr[i] != -1:
if [hl[i],hr[i]] not in hole:
res += (hl[i]-hr[i]-1)*(min(height[hl[i]],height[hr[i]])-height[i])
hole.append([hl[i],hr[i]])
#print(res)
i += 1
return res
整合单调栈
每次找到右边更大的,就把前面坑里的水算一下。
height = [0,1,0,2,1,0,1,3,2,1,2,1]
- res = 0, stack = [0]
- 1>0, bottle = 0, stack = []不进if,stack = [1]
- 0<1, stack = [1,2]
- 2>0, bottle = 2, stack = [1]进if, res = 1, stack = [3]
- 1<2, stack = [3,4]
- 0<1, stack = [3,4,5]
- 1>0, bottle = 0, stack = [3,4]进if, res = 2, 但1==1, stack = [3,4,6]
- 3>1, bottle = 1, stack = [3,4]进if, res = 3, 3>0继续
bottle = 1, stack = [3]进if, res = 5, 3>1继续
bottle = 1, stack = []不进if
…
class Solution:
def trap(self, height: List[int]) -> int:
res = 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]]:
bottle = stack.pop()
if stack:
h = min(height[stack[-1]],height[i])-height[bottle]
w = i - stack[-1]-1
#print(h,w)
res += h*w
stack.append(i)
return res
风语者!平时喜欢研究各种技术,目前在从事后端开发工作,热爱生活、热爱工作。