吃透单调栈（1）——单调栈入门

2023-09-03 10:56 由 blogzzt 发表于 #其他

单调栈是一种理解起来很容易，但是运用起来并不那么简单的数据结构。一句话解释单调栈，就是一个栈，里面的元素的大小按照他们所在栈内的位置，满足一定的单调性。

单调栈摸版

下面维护一个顶大底小的的单调栈

stack<int> st;
for(int i = 0; i < nums.size(); i++)
{
    while(!st.empty() && st.top() > nums[i])
    {
        st.pop();
    }
    st.push(nums[i]);
}

开胃小菜

题目是这样的，给一个数组，返回一个大小相同的数组。返回的数组的第i个位置的值应当是，对于原数组中的第i个元素，至少往右走多少步，才能遇到一个比自己大的元素（如果之后没有比自己大的元素，或者已经是最后一个元素，则在返回数组的对应位置放上-1）。

简单的例子：

input: 5,3,1,2,4

return: -1 3 1 1 -1

explaination: 对于第0个数字5，之后没有比它更大的数字，因此是-1，对于第1个数字3，需要走3步才能达到4（第一个比3大的元素），对于第2和第3个数字，都只需要走1步，就可以遇到比自己大的元素。对于最后一个数字4，因为之后没有更多的元素，所以是-1。

暴力做的结果就是O(n^2)的时间复杂度，例如对于一个单调递减的数组，每次都要走到数组的末尾。那么用单调栈怎么做呢？先来看代码：

vector<int> nextExceed(vector<int> &input) {
    vector<int> result (input.size(), -1);
    stack<int> monoStack;
    for(int i = 0; i < input.size(); ++i) {    
        while(!monoStack.empty() && input[monoStack.top()] < input[i]) {
            result[monoStack.top()] = i - monoStack.top();
            monoStack.pop();
        }
        monoStack.push(i);
    }
    return result;
}

我们维护这样一个单调递减的stack，stack内部存的是原数组的每个index。每当我们遇到一个比当前栈顶所对应的数（就是input[monoStack.top()]）大的数的时候，我们就遇到了一个“大数“。这个”大数“比它之前多少个数大我们不知道，但是至少比当前栈顶所对应的数大。我们弹出栈内所有对应数比这个数小的栈内元素，并更新它们在返回数组中对应位置的值。因为这个栈本身的单调性，当我们栈顶元素所对应的数比这个元素大的时候，我们可以保证，栈内所有元素都比这个元素大。对于每一个元素，当它出栈的时候，说明它遇到了自己的next greater element，我们也就要更新return数组中的对应位置的值。如果一个元素一直不曾出栈，那么说明不存在next greater element，我们也就不用更新return数组了。

举一反三

下面用相同的套路做一道Leetcode题：1475. 商品折扣后的最终价格

 vector<int> finalPrices(vector<int> &input)
    {
        // 单调栈实现 O（1）
        vector<int> result = input;
        stack<int> monoStack;
        for (int i = 0; i < input.size(); ++i) {
            while (!monoStack.empty() && input[monoStack.top()] >= input[i]) {
                result[monoStack.top()] = input[monoStack.top()] - input[i];  // 更新
                monoStack.pop();  // 出栈  （注意，每个元素仅出栈一次）
            }
            monoStack.push(i);
        }
        return result;
    }