基础思路:
需要选出基准元素,选出左边第一个比它小的柱子,以及右边第一个比它小的柱子。
单调栈的应用:
当遍历到的元素小于栈顶元素时,栈顶元素是基准元素,遍历到的元素是右边第一个比它小的柱子,和栈顶相邻的栈内元素是左边第一个比它小的柱子。
面积求解:h是基准柱子的高,w是right-left-1。
首尾加0:首部加0是因为当原数组是单调递减的,为了确保栈顶元素弹出后栈内依然有元素,在数组首部进行加0;
尾部加0是因为当原数组是单调递增的,当数组内所有元素全部入栈,栈内元素满足单调递减,结果无法得出,尾部加0可以实现遍历到的元素小于栈顶元素,从而得出结果。
代码实现: