栈这个数据结构有很多有趣的用途,这里总结一个很有用的使用方式,单调栈。单调队列同理,仅是后入先出变成先入先出。

单调栈


  单调栈是在满足数据后入先出的前提下,栈内数据满足单调递增或单调递减排列。

  如单调递增栈:数据 i 入栈,先判断当前栈顶数据是否小于 i ,若不满足则弹出栈顶数据,直到栈顶数据小于 i 或栈为空,再将 i 入栈。这样保证了任意数据 i 入栈时,栈中所有元素小于 i,且满足先后顺序。

  我们考虑一个算法场景:给定一个非有序排列的数组 num[n],求数组中下标为 i 的数 num[i],其向左遍历第一个小于 num[i]的数。 如果我们无脑遍历,则需要在遍历数组本身的同时,从每一个 i 前向遍历出第一个小于 num[i] 的数。 算法复杂度在最坏情况下为 $$n^2$$。而若我们 使用单调栈,则能在只遍历一次数组 num 的同时,找出所有要求的数 ,算法复杂度降低到 $$n$$。因为当每一个数据 i 可以入栈时,当前单调栈栈顶的数就是满足要求的数。

例: num[] = {1, 2, 2, 5, 4, 3 }. 用 index 表示数组下标. 过程如下 :

  • index = 0, 栈为 [ ], num[0] 入栈,满足要求的数为空.
  • index = 1, 栈为 [1],栈顶 < num[1],num[1] 入栈,满足要求的数为入栈时栈顶: 1.
  • index = 2, 栈为 [1, 2],栈顶 >= num[2],栈弹出一个,num[2] 入栈,满足要求的数为入栈时栈顶: 1.
  • index = 3, 栈为 [1, 2],栈顶 < num[3],num[3] 入栈,满足要求的数为入栈时栈顶: 2.
  • index = 4, 栈为 [1, 2, 5],栈顶 >= num[4],栈弹出一个,num[4] 入栈,满足要求的数为入栈时栈顶: 2.
  • index = 5, 栈为 [1, 2, 4],栈顶 >= num[5],栈弹出一个,num[5] 入栈,满足要求的数为入栈时栈顶: 2.
  • 此时,一遍遍历完成,已经找出所有要求的数,对应分别是 [null, 1, 1, 2, 2, 2]

算法实例


leetcode 第84题:largest-rectangle-in-histogram

解法如下:

class Solution {
public:
int largestRectangleArea(vector<int>& heights) {
    unsigned long size = heights.size();
    int maxSize = 0;

    stack<int> rectStack;
    vector<int> leftIndex(size);
    for (int index = 0; index < size; index++){
        while (!rectStack.empty() && heights[rectStack.top()] >= heights[index])
            rectStack.pop();
        if (rectStack.empty())
            leftIndex[index] = 0;
        else
            leftIndex[index] = rectStack.top() + 1 ;
        rectStack.push(index);
    }
    while (!rectStack.empty()) rectStack.pop();
    for (int index = size - 1; index >= 0; index--){
        while (!rectStack.empty() && heights[rectStack.top()] >= heights[index])
            rectStack.pop();
        int rightBound = 0;
        if (rectStack.empty())
            rightBound = size - 1;
        else
            rightBound = rectStack.top() - 1;
        rectStack.push(index);
        int currentSize = heights[index] * (rightBound - leftIndex[index] + 1);
        maxSize = currentSize >= maxSize ? currentSize : maxSize;
    }

    return maxSize;
 }
};

标签: 算法

添加新评论