作者：用户geafr1kx8g | 来源：互联网 | 2023-05-17 07:15
今天在qq群了看到了这个题目，觉得用单调栈的解法挺好，可以在o（n）内搞定，特意记录下来首先明确单调栈的含义：栈是FILO的，栈的所有操作都是在栈顶进行。单调性指的是当前栈中存储的元素是严
今天在qq群了看到了这个题目，觉得用单调栈的解法挺好，可以在o（n）内搞定，特意记录下来
首先明确单调栈的含义：
栈是FILO的，栈的所有操作都是在栈顶进行。
单调性指的是当前栈中存储的元素是严格的递增或者递减。
递增：栈中元素从栈顶到栈底是严格递增的； 递减：栈中元素从栈顶到栈底是严格递减的。
举例：先后入栈的元素假设为9,3,10,1,15。。
考虑递增栈：
初始时，栈为空；
9入栈，栈当前为（9）
3入栈，栈不变
10入栈，9出栈，栈当前为（10）
1入栈，栈不变
15入栈，10出栈，栈当前为（15）
本题目解读：(群中出题者给的例子)
举例:
输入={1, 4, 2, 3}
初始标记都是0={0, 0, 0, 0}
取子区间[1, 4] 最大数是4 所以4做一次标记 标记变为{0, 1, 0, 0}
子区间[1, 3] 最大数还是4 {0, 2, 0 ,0}
[1, 2] {0, 3, 0, 0}
……
这样遍历所有的n*(n-1)/2子区间之后 输出当前标记数组即可
解题思路：依次遍历每个数，利用单调栈的思路，找到每个数前面第一个比它大的数，再找到后面第一个比它大的数。然后直接计算当前数对应的结果。。
比如说：{5，1, 4, 2, 3，6}
假设当前遍历到了数4，则前面第一个比它的是5，后面第一比它大的是6，显然，当某个子序列最大值为4时，这个子序列不能包含5和5前面的数，也不能包含6和6后面的数，所以直接考虑区间{1,4,2,3}中4能作为最大数的子序列个数count,count即为4对应的最后结果。
计算公式：假设4前面数的个数为m（这些数均小于4），4后面的个数为n（这n个数均小于4），m和n可以由下标计算得到，于是有：
（1）4不作为序列边界的序列数count1 = m * n;
（2）4作为序列边界的序列数count2 = m + n;
所以可知: count = count1+count2 = m*n+m+n;
依次计算每个数的count值，即可在o(n)内解决这道题。
京公网安备 11010802041100号