image.png
获取数组每个值的 相邻左边比值小的数和相邻右边比值小的数
使用一个从小到大的栈
image.png
遍历数组，如果栈为空，则将当前位置压栈，如果当前位置的数比栈顶位置的数大，则将当前位置压栈，如果当前位置的数比栈顶位置的数小，则将栈里的数弹出，弹出位置数的相邻左边小值为弹出后的栈顶位置数，相邻右边小值为当前位置数。
当数组遍历完，栈里还有数，则依次弹出，弹出位置的相邻右边小值为空，左边小值为弹出后的栈顶位置。
-
求直方图中能形成的最大矩形。
image.png
image.png
-
定义一个值 Q = 数组中所有数的和 * 数组的最小值，每个子数组可以求一个Q，求最大的Q是多少。
数组都为正值。
image.png 同直方图题
image.png
穷举所有矩形，以数组代表一个压缩矩形
image.png
时间复杂度O(m*n)
- 环形山数组 【3,2,1,4,5】
image.png
若数组无重复数字，则时间复杂度为O(1)
每个点以最小姿态去找能看到的山峰，则除了最高的山和第二高的山，其他山都可以看到2个山峰。
数字数量 对数
1 0
2 1
3 2
n 2*(n-2)+1
image.png
若有重复，则使用一个从大到小的单调栈。
栈中放Map<数字，个数>
遍历数组，若当前数比栈顶的数大，则弹出栈顶，对数加C(k,2)+2k (C()排列组合,k为栈顶数个数)，若当前数比栈顶小，则直接进栈，若当前数与栈顶相等，则栈顶的个数加1。
遍历完后，栈中数依次弹出，结算公式仍未C(k,2)+2k 直到栈中只剩2个数。对于倒数第二条数据，若最后一条数据个数只有一个，则结算公式为C(k,2)+1k,否则为C(k,2)+2k。
最后一条数据的结算公式为 C(k,2)。
image.png
