1、算法的基本目标
「概念」单调递增栈就是栈内元素满足单调递增,假设当前元素为 x,若栈顶元素 ≤ x ,则将 x 入栈,否则不断弹出栈顶元素,直至栈顶元素 ≤ x
[目标]求得每一个数字在原始序列中左 / 右边第一个大于 / 小于它自身的数字。
[拓展——单调递减栈]求得每一个数字在原始序列中右边/左边第一个小于/大于它自身的数字。
2、算法的思想步骤:
以单调递减栈为例,求得num[ ]数组中每一个数字在原始序列中右边第一个大于它自身的数字。
以nums2 = [2, 3, 5, 1, 0, 7, 3] 为例
step1:首先当前栈为空,将num[0]元素压入栈;此时栈中的元素为2
step2:遍历到第二个元素num[1]=3,将其与栈顶元素进行比较,此时该元素严格大于栈顶元素num[0]=2,找到num[0]右边的第一个大于其自身的数字,并将栈顶元素弹出,此时栈为空,将当前元素num[1]压入栈;
step3:遍历到第三个元素num[2]=5,将其与栈顶元素进行比较,此时该元素严格大于栈顶元素num[1]=3,找到num[1]右边的第一个大于其自身的数字,并将栈顶元素弹出,此时栈为空,将当前元素num[2]压入栈,此时栈中的元素为【5】;
step4: 遍历到第四个元素num[3]=1,将其与栈顶元素进行比较,此时该元素严格小于栈顶元素num[2]=5,将当前元素压入栈。此时栈中的元素为【5,1】;
step5:遍历到第五个元素num[4]=0,将其与栈顶元素进行比较,此时该元素严格小于栈顶元素num[3]=1,将当前元素压入栈,此时栈中的元素为【5,1,0】;
step6: 遍历到第六个元素num[5]=7,将其与栈顶元素进行比较,此时该元素严格大于栈顶元素num[4]=0,找到num[4]右边的第一个大于其自身的数num[5]=7,并将栈顶元素num[4]=0弹出;此时栈不为空,继续将当前元素num[5]=7与栈顶元素num[3]=1相比,该元素严格大于栈顶元素,找到num[3]右边的第一个大于大于其自身的数,依次循环,直至栈为空或者当前元素小于栈顶元素,将当前元素压入栈顶;此时栈中的元素为【7】;
step7:遍历到第7个元素num[6]=0,将其与栈顶元素进行比较,此时该元素严格小于栈顶元素num[5]=7,将其压入栈,此时栈中的元素为【7、3】;
step8: 当num数组遍历完成,此时栈中还有元素,依次弹出栈顶元素为3和7。
至此,栈中元素弹出的顺序为【2,3,0,1,5,3,7】
