Python版day59

503. 下一个更大元素 II

给定一个循环数组 nums （ nums[nums.length - 1] 的下一个元素是 nums[0] ），返回 nums 中每个元素的 下一个更大元素 。

数字 x 的 下一个更大的元素 是按数组遍历顺序，这个数字之后的第一个比它更大的数，这意味着你应该循环地搜索它的下一个更大的数。如果不存在，则输出 -1 

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/next-greater-element-ii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

class Solution:def nextGreaterElements(self, nums: List[int]) -> List[int]:n = len(nums)res = [-1]*n# 下一个更大元素->栈头到栈尾单调递增# 2*len 循环数组，把这个数组拼接一下stack = []for i in range(2*n):while(len(stack)!=0 and nums[i%n]>nums[stack[-1]]):res[stack[-1]] = nums[i%n]stack.pop()stack.append(i%n)return res

 42. 接雨水

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。 

class Solution:def trap(self, height: List[int]) -> int:if len(height) <=2:return 0stack = []# 栈头到栈尾从小到大的顺序stack.append(0)sum_ = 0for i in range(1,len(height)):# 情况1直接入栈if height[i]<height[stack[-1]]:stack.append(i)elif height[i]==height[stack[-1]]:# 因为相等的相邻墙，左边一个是不可能存放雨水的，所以pop左边的index, push当前indexstack.pop()stack.append(i)else:stackTop = stack[-1]while (len(stack)!=0 and height[i]>height[stackTop]):# mid是凹槽底部mid = stack.pop()if len(stack)!=0:left = stack[-1]# 左右墙最小高度减去凹槽高度h = min(height[left] ,height[i])-height[mid]w = i-left-1hold = h*wif hold>0:sum_ +=holdstackTop = stack[-1]stack.append(i)return sum_