家用电脑做网站能备案,wordpress 婚庆主题,检察院网站建设自查报告,html5 个人网站模板目录 503.下一个更大元素II思路代码 42. 接雨水思路一 双指针思路二 单调栈代码 84.柱状图中最大的矩形思路一 双指针思路二 单调栈代码 503.下一个更大元素II
Leetcode
思路
将数组乘2来遍历即可#xff0c;就是加长版的每日温度。
但是处理起来会有细节#xff0c;如果… 目录 503.下一个更大元素II思路代码 42. 接雨水思路一 双指针思路二 单调栈代码 84.柱状图中最大的矩形思路一 双指针思路二 单调栈代码 503.下一个更大元素II
Leetcode
思路
将数组乘2来遍历即可就是加长版的每日温度。
但是处理起来会有细节如果只是单纯数组乘二最后返回的时候还需要返回数组的一半大小空间上不是很划算。
其实不需要扩大数组只需要在遍历的时候遍历长度为2*len(nums), 然后nums[i % len(nums)]即可。
代码
数组乘2
class Solution:def nextGreaterElements(self, nums: List[int]) - List[int]:nums nums numsres [-1] * len(nums)stack [0]for i in range(1, len(nums)):if nums[i] nums[stack[-1]]:stack.append(i)else:while stack and nums[i] nums[stack[-1]]:res[stack[-1]] nums[i]stack.pop()stack.append(i)return res[:len(nums)//2]遍历长度为2*len(nums)
class Solution:def nextGreaterElements(self, nums: List[int]) - List[int]:dp [-1] * len(nums)stack []for i in range(len(nums)*2):while(len(stack) ! 0 and nums[i%len(nums)] nums[stack[-1]]):dp[stack[-1]] nums[i%len(nums)]stack.pop()stack.append(i%len(nums))return dp42. 接雨水
Leetcode
思路一 双指针
对于每一个柱子用两个list分别存放左边最高的柱子和右边最高的柱子。 列4 左侧最高的柱子是列3高度为2以下用lHeight表示。
列4 右侧最高的柱子是列7高度为3以下用rHeight表示。
列4 柱子的高度为1以下用height表示
那么列4的雨水高度为 列3和列7的高度最小值减列4高度即 min(lHeight, rHeight) - height。
在有了rHeight和lHeight的情况下遍历所以的柱子求出雨水体积即可。
思路二 单调栈
单调栈按照行方向来计算雨水体积
代码
双指针
class Solution:def trap(self, height: List[int]) - int:lHeight, rHeight [0] * len(height), [0] * len(height)lHeight[0] height[0]for i in range(1, len(lHeight)):# 计算左边最高柱子的时候连自己也包括lHeight[i] max(lHeight[i - 1], height[i])rHeight[-1] height[-1]for i in range(len(rHeight) - 2, -1, -1):rHeight[i] max(rHeight[i 1], height[i])res 0for i in range(len(height)):res (min(rHeight[i], lHeight[i]) - height[i])return res单调栈
class Solution:def trap(self, height: List[int]) - int:stack [0]result 0for 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]# 雨水宽度是 凹槽右侧的下标 - 凹槽左侧的下标 - 1w i - stack[-1] - 1# 累计总雨水体积result h * wstack.append(i)return result84.柱状图中最大的矩形
Leetcode 思路一 双指针
对于每一个柱子用两个list分别存放左边第一个小于该柱子的下标和右边第一个小于该柱子的下标。
在有两个list的基础上遍历heights,
res heights[i] * (minRightIndex[i] - minLeftIndex[i] - 1)
思路二 单调栈
思路来源neetcode
代码
单调栈
class Solution:def largestRectangleArea(self, heights: List[int]) - int:maxArea 0stack []for i, h in enumerate(heights):start iwhile stack and stack[-1][1] h:index, height stack.pop()maxArea max(maxArea, height * (i - index))start indexstack.append([start, h])for i, h in stack:maxArea max(maxArea, h * (len(heights) - i))return maxArea
