day49

42、接雨水(超经典):接雨水就是求凹槽的面积,每一列凹槽的面积由它左边的第一个比它高的柱子和右边第一个比它高的柱子决定的,两者的最小值减去当前列的柱子高度即为凹槽的高度,所以很适合用单调栈求解。单调递增栈,如果新元素比栈顶元素小或相等则入栈(下标入栈),说明还没找到右边第一根比它高的柱子;如果新元素比栈顶元素大,则说明找到了栈顶元素的右边第一根比它高的柱子,左边比它高的柱子则已经在栈里了。

84、柱状图中最大的矩形:关键是要找到每根柱子左右两边第一个更小的柱子。单调递减栈:当比栈顶元素大或相等则入栈,小则取栈顶元素作为矩形的高度,宽度则为左右两边更小的柱子的下标差。在数组首尾分别加上0,方便计算宽度
全部评论

相关推荐

评论
点赞
收藏
分享
牛客网
牛客企业服务