day49
42、接雨水(超经典):接雨水就是求凹槽的面积,每一列凹槽的面积由它左边的第一个比它高的柱子和右边第一个比它高的柱子决定的,两者的最小值减去当前列的柱子高度即为凹槽的高度,所以很适合用单调栈求解。单调递增栈,如果新元素比栈顶元素小或相等则入栈(下标入栈),说明还没找到右边第一根比它高的柱子;如果新元素比栈顶元素大,则说明找到了栈顶元素的右边第一根比它高的柱子,左边比它高的柱子则已经在栈里了。
84、柱状图中最大的矩形:关键是要找到每根柱子左右两边第一个更小的柱子。单调递减栈:当比栈顶元素大或相等则入栈,小则取栈顶元素作为矩形的高度,宽度则为左右两边更小的柱子的下标差。在数组首尾分别加上0,方便计算宽度
84、柱状图中最大的矩形:关键是要找到每根柱子左右两边第一个更小的柱子。单调递减栈:当比栈顶元素大或相等则入栈,小则取栈顶元素作为矩形的高度,宽度则为左右两边更小的柱子的下标差。在数组首尾分别加上0,方便计算宽度
全部评论
相关推荐
点赞 评论 收藏
分享
01-25 15:42
蚌埠坦克学院 后端工程师 牛客10001:我也宿舍,想不到还能去哪啊,图书馆教室都有人吧,找个没人的楼道或者啥的还忒背着死沉的游戏本,面试时间太长没电了咋整,学校那个面试间至今没搞懂咋开门
点赞 评论 收藏
分享
查看11道真题和解析