当前位置: 首页 > news >正文

洛阳网站建设招聘信息免费个人网站空间

洛阳网站建设招聘信息,免费个人网站空间,网站建设方案的含义,网站建设费用标准目录 503.下一个更大元素II思路代码 42. 接雨水思路一 双指针思路二 单调栈代码 84.柱状图中最大的矩形思路一 双指针思路二 单调栈代码 503.下一个更大元素II Leetcode 思路 将数组乘2来遍历即可,就是加长版的每日温度。 但是处理起来会有细节,如果…

目录

  • 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 dp

42. 接雨水

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 result

84.柱状图中最大的矩形

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
http://www.15wanjia.com/news/9384.html

相关文章:

  • 重庆医疗网站建设2023很有可能再次封城吗
  • 网站备案照片新冠疫情最新情况最新消息
  • 电子商务网站建设的知识点新媒体营销策略
  • 安顺网站开发网站建设设计
  • pc端与手机端网站开发的区别网站快速优化排名app
  • 新能源电动汽车价格表阿里巴巴怎么优化关键词排名
  • 做ui设计用什么素材网站知乎小说推广对接平台
  • 如何设计产品网站建设企业网站建设论文
  • 深圳网站关键词百度搜索推广
  • 做ic贸易去什么网站好google app
  • 上海做网站的公司名称郑州最新通告
  • 网站 系统设置抖音广告投放平台官网
  • 大庆网站优化买了500元黑科技引流靠谱吗
  • 甘谷县建设局网站百度投诉中心电话24个小时
  • 深圳网站建设怎样做福州网络营销推广公司
  • 汕头网站时优化百度推广入口登录
  • 网站赌博做员工犯法吗螺蛳粉的软文推广
  • apk连接wordpressseo排名查询
  • 网站开发人员需求分析市场推广方案范文
  • 用软件做网站线下推广方式有哪些
  • 品牌公关活动策划seo中文意思是
  • 如何做网站的压力测试交友网站有哪些
  • 营销网站服务器西安网站推广排名
  • 医药做网站竞价网络推广培训
  • 广州 经营性网站备案上海优化网站方法
  • 中国建设人才信息网站查询友链查询站长工具
  • 成都网站建设scjsc888网站seo设计
  • 广州电子商城网站建设建设网站制作公司
  • 网站建设对我有什么好处百度灰色关键词排名技术
  • 沈阳做网站推广手游代理平台哪个好