单调栈
概念
单调递增栈:
在一个队列中针对每一个元素从它右边寻找第一个比它小的元素
在一个队列中针对每一个元素从它左边寻找第一个比它小的元素
单调递减栈:
在一个队列中针对每一个元素从它右边寻找第一个比它大的元素
在一个队列中针对每一个元素从它左边寻找第一个比它大的元素
单调栈何时用:为任意一个元素找左边和右边第一个比自己大/小的位置用单调栈.
单调递增栈用于找到当前元素左边第一个小于它的的元素
例如:54361207,这个数组获得左边和右边第一个比自己大的位置.使用让数组依次进入单调栈,0位置的5进栈,1位置的4进栈,2位置的3进栈,当4位置的6进栈时,为了保证栈的单调性,需要依次将2->3、1->4、0->5出栈,只要一个数据开始弹出,它的信息就开始生成,左边第一个比自己大的数就是栈中被自己压的数,右边第一个比自己大的数就是让自己弹出的数。对于2->3来说,左边是0->4,右边是4->6。
数组遍历完之后,如果栈中还存在数据,就依次弹出数据,只有左边第一个比自己大的数,就是栈中被自己压的数。因为每个数据只进栈和出栈一次,所有时间复杂度为O(n)
.
单调栈可以处理有重复值的数据。对于值重复的数据,在栈中压在一起,采用的链表的方式处理。
例如:43245,当3->4进栈时,将它和0->4压在一起,用链表连接。最后出栈的时候一起出栈。
问题
定义:数组中累积和与最小值的乘积,假设叫做指标A。给定一个数组,请返回子数组中,指标A最大的值。
以数组中每个数为最小值,求包含它的子数组的指标A,最后求最大值。