乐趣区

关于算法-数据结构:单调栈是啥

笔者最近在刷 LeetCode 习题,故想将一些经典算法以及一些经典的数据结构汇编成一个系列,分享给大家和当前的本人。本文次要波及 枯燥栈

枯燥栈

枯燥栈自身的概念并不难理解,然而理论利用起来须要了解粗浅才行。笔者当初了解了一个早晨才弄明确,而你们只须要看完这半篇文章即可齐全了解。

对于递增栈和递加栈很多中央说法不一,此处为了不便阐明,将栈底到栈顶枯燥增的即为递增栈;枯燥减的即为递加栈。(不肯定正确,然而不影响之后的了解)。

先探讨递增栈,此处我定义一个概念:极左邻元素和极右邻元素。假如数组 nums,其中以后元素的下标为 k,那么若满足 nums[q] < nums[k],且在区间 [q+1,k-1] 中的元素全都大于 nums[k]。那么 nums[q]即为 nums[k]的极左邻元素,同理能够定义极右邻元素。

递加栈中相似,此处不再赘述。

光看下面的定义的确很好了解,让咱们来思考一下枯燥栈的作用。它可能帮忙咱们找到以后元素的极左邻元素和极右邻元素,从而实现一些性能。搬一道经典题目,

链接:https://leetcode-cn.com/problems/largest-rectangle-in-histogram/

给定 n 个非负整数,用来示意柱状图中各个柱子的高度。每个柱子彼此相邻,且宽度为 1。求在该柱状图中,可能勾画进去的矩形的最大面积。

图中暗影局部为所能勾画出的最大矩形面积,其面积为 10 个单位。

此题若采纳暴力搜寻的形式诚然很简单,其实用枯燥栈即可在 O(n)的工夫内解决。大家先了解一个“扩散”的概念,假如我当初抉择倒数第二个柱子(值为 2),要想以此为核心,勾画出最大的矩形,那么从这个柱子开始,左右扩散。右边的柱子比本人高,扩散胜利,左边的柱子也比本人高,扩散胜利。所以最终能够扩散到 [5,6,2,3] 这几根柱子上,那么以以后这个柱子为高,所能勾画最大矩形面积即为 2 *4 = 8。那么这种“扩散”是在哪里进行的呢?显然,是在比以后元素小的且离以后元素最近的元素进行,这不就是上文中提到的 极左邻元素 嘛!所以只有能确定每个元素的极左邻元素和极右邻元素,那么间接一减就是宽度了呀。

如何利用枯燥栈找极左邻、极右邻元素?

保护一个递增栈。留神:栈中放的是元素的下标。要获取元素比大小的话,间接通过下标去数组中找就好了。

枯燥栈的代码模板

int stack_F(vector<int>& nums){
    int maxx;
    stack<int>st;
    // 此处的 - 1 是比 nums 中所有数都要小的数,也能够 -1000,本人定。次要是为了让栈中的所有元素都能够被弹出,因为要保护枯燥栈,遇到一个很小的数,栈中的元素必定全都会被弹出来。有利于将所有解都遍历到。nums.push_back(-1);
    for(int i=0;i<nums.size();i++){
        // 此处等号可取可不取
        if(st.empty() || nums[st.top()] <= nums[i]){
            // 存的是下标哦!st.push(i);
        }
        else{while(!st.empty() && nums[st.top()] > nums[i]){
                // 留神你是站在栈顶元素的立场来看的喔!int index = st.top();st.pop();
                int left_boder = st.top();
                int right_boder = i;
                // 有了这些边界点,就能够自定义统计左右符合条件的数量啦!比拟 maxx 的值等。//your code ...
            }
            st.push(nums[i]);
        }
    }
    return maxx;
}

至此 枯燥栈 就完结了,下次更新的主题《递归的好基友,动静布局?啥是无后效性?》,欢送点赞珍藏!

退出移动版