1、算法原理

以单调递增栈来讲解单调栈原理。假设当前元素为x，

(1) 若x < 栈顶元素，那就不满足单调递增性，这时将栈中元素y弹出，若此时条件仍然不满足，则继续弹出栈顶元素，直到满足条件，再将x入栈;

(2) 若x >= 栈顶元素，满足单调递增性，将x入栈；

如此不断重复以上步骤，直到所有满足条件的元素都入栈。

以一个具体例子[3, 5, 2, 6, 8]为例：

（1）首先将3入栈，此时栈中元素为[3];

（2）再将5入栈，此时栈中元素为[3, 5];

（3）再将2入栈，发现此时2 < 5，不满足单调递增性，将5出栈，2入栈。此时栈中元素应为[3, 2]，依然不满足单调递增，继续（4）步骤;

（4）将栈顶元素3出栈，再将2入栈，此时栈中元素为[2]；

（5）将6和8依次入栈，最终栈中元素为[2, 6, 8]。

2、实例

单调栈常常用来解决“下一个更大元素”之类的问题，如LeetCode 1475. 商品折扣后的最终价格题。

给你一个数组 prices ，其中 prices[i] 是商店里第 i 件商品的价格。

商店里正在进行促销活动，如果你要买第 i 件商品，那么你可以得到与 prices[j] 相等的折扣，其中 j 是满足 j > i 且 prices[j] <= prices[i] 的最小下标，如果没有满足条件的 j ，你将没有任何折扣。

请你返回一个数组，数组中第 i 个元素是折扣后你购买商品 i 最终需要支付的价格。

示例：
输入：prices = [10,1,1,6]
输出：[9,0,1,6]

这是一道典型的单调栈题目，单调栈解法如下：

int* finalPrices(int* prices, int pricesSize, int* returnSize){
    *returnSize = pricesSize;
    int *ret = (int *)malloc(sizeof(int)*pricesSize);
    int stk[pricesSize];
    int top = 0;
    memcpy(ret, prices, sizeof(int)*pricesSize);

    for (int i = 0; i < pricesSize; i++) {
        while (top != 0 && prices[i] <= prices[stk[top-1]]) {
            ret[stk[top-1]] = prices[stk[top-1]] - prices[i];
            top--;
        }
        stk[top++] = i;
    }
    return ret;
}

几乎所有的单调栈问题都可以套用以上的模板来解决，只需要根据实际情况稍作调整即可。

发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/190635.html原文链接：https://javaforall.net