求一个数组中的每个i位置的,左边比i位置值大的,且离i位置最近的位置,以及右边比i位置值大的,且离i位置最近的位置。

经典方法:分别遍历,O(N2)
单调栈解法思路:
假设数组中没有重复值
- 准备一个栈,要求栈内数据从栈底到栈顶数据从大到小排序,栈内存放数据的下标
- 依次遍历数组内的数据,当遍历的数据比栈顶数据小时,直接入栈(此时栈内的所有数据都可以确定他们的左边较大值);当遍历的数据比栈顶数据大时,依次出栈数据,直到栈顶的数据比他大,然后将该数据入栈,依次出栈的数据就都可以确定他们的右边较大值,于是这些出栈的数据可以输出结果。
假设数组中有重复值:
-
如果遇到入栈数据和栈顶数据一样的,将两个下标表示在一次,即他们可以同时确定右边界。
- 当要弹出的数据的左边界内有多个下标时,选择最靠近它的,即最大的下标作为它的左边界。
应用1:
定义:数组中累加和与最小值的乘积,假设叫做指标A。
给定一个数组(都为正数),请返回子数组中,指标A最大的值。
思路:
- 求出数组中的每个值,其作为最小值时能得到最大指标A的子数组。
- 用单调栈找到左右两边第一个比他小的值,那么中间的数就是要求的子数组。
