大家好，又见面了，我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。
Jetbrains全系列IDE使用 1年只要46元 售后保障 童叟无欺
单调栈，是指栈内元素从栈底到栈顶单调递增或单调递减的栈。简单来讲，单调栈=单调 + 栈，它同时满足两个特性：单调性、栈。
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
