单调栈的认识及其应用

什么是单调栈

单调栈就是栈里面存放的数据都是有序的,所以可以分为单调递增栈和单调递减栈两种。

    1. 单调递增栈就是从栈底到栈顶是从大到小
    2. 单调递减栈就是从栈底到栈顶是从小到大

    case1:给定一个数组,让构建一个所有子树的根节点都是最大的一颗二叉树

                   首先想到就是大根堆,但是我们的单调栈也能解决如上问题

-----------------------------------------------------------------------------------------------------------------------------------------

leetcode上的接雨水问题

 

单调栈可以解决两边比它小的就停止,不然向左右扩张,按照   长*宽的办法分别记录里面的值,最后获取到最大的值max

原文地址:https://www.cnblogs.com/whr-blogs/p/updown_stack.html