A - 单调栈

题目大意

给出项数为 n 的整数数列 1…a1…n。

定义函数 f(i) 代表数列中第 i* 个元素之后第一个大于 a i 的元素的下标，即 f(i)=\min_{i a_i} {j}。若不存在，则。若不存在，则f(i)=0。

试求出 f(1…n)。

解题思路

刚开始写的时候一知半解，直到昨晚B题才理解单调栈。

其实单调栈就是一种查询方式，用空间换时间来降低时间复杂度。

举个例子，我们要找的是当前数后面第一个大于他的数，如果不出意外，遍历到的数符合条件，就执行操作并清空栈，并把遍历到的数入栈，然后遍历下一个书。如果遍历到的这个数不符合条件呢？我们让他入栈来代命，再继续看下一个数符不符合，如果终于找到了一个符合条件的数，那么其实这个数对于前面一系列入栈的数都是符合条件的。例如4，3，2，1，4，前四个数递减，全部入栈了，直到第五个数终于递增了，3，2，1都是比4小的，所以3，2，1要对应的数都是这个4。而第一个4继续留在栈里，等待后续查找。

所以的话，对于这题，可以这么写单调栈：遍历数列，栈空的话就把他的下标入栈，遇到的数比栈顶数小就把这个数的下标入栈，遇到的数比栈顶数大就把这个数的下标存在临时数组里，栈顶数出栈，然后再次比较栈顶数和当前数，直到栈顶数大于当前数。全部执行完后如果栈里还有数，说明他是最后一个数，后面没有比它大的数了，在临时数组里标记为0。最后按照顺序依次输出临时数组里的数（下标）就好了。

B - 发射站

题目大意

某地有 N 个能量发射站排成一行，每个发射站 i 都有不相同的高度 H i，并能向两边（两端的发射站只能向一边）同时发射能量值为 V i 的能量，发出的能量只被两边最近的且比它高的发射站接收。显然，每个发射站发来的能量有可能被 0 或 1 或 2个其他发射站所接受。

请计算出接收最多能量的发射站接收的能量是多少。

解题思路

这里单调栈用来储存下标，即元素的位置。

想了挺久才懂，其实单调栈就是找离元素最近的大于他或小于他的元素的位置，实现过程就是把元素每次跟栈顶元素作比较，符合条件就执行一次操作，并且弹出栈顶元素，不符合条件就把这个数入栈待命，等到下一次出现符合条件的元素，那么前面待命的元素就均与当前这个元素匹配。

举个例子就很好理解：单调递增栈，假设有这么一串数：1,4,3,2,5。4大于1，就执行一次操作，然后把1从栈里踢掉，4入栈，这样4就成了下一轮被比较的元素。3比4小，不符合，那就入栈待命，2也比3小，再入栈待命。然后发现5大于2，终于符合了，而实际上5对于4,3,2都是符合的，而由于我入栈的时候是递减的，所以用5把栈顶的元素一个一个踢掉就好了，然后又让5入栈。。。上一次操作中已经把1给踢掉了，所以不用担心会出现5和前面1比较的情况。

了解完这些之后再来看这道题就比较好懂了。

开三个数组分别存高度，发射的能量，积累的能量，下标表示他们的位置，然后遍历数组。

向右发射就和上面的操作一样，符合就累积一下能量，然后去掉栈顶元素（他发射完了），不符合就入栈。也可以看成，自己左边那些比自己矮的元素的能量都被自己吸走了，比如4,3,2,1,5,这个例子，4321的能量都要累加到5的位置上。

向左发射的话可以这么考虑，由于单调栈的特性，这里入栈的元素都是递减的，所以当不符合的时候，当前元素的能量就发射给栈顶元素。这里每次一次循环只发射一次，和之前向右发射的吸收多个能量有所区别。举个例子，有4,3,2,1,5几个数，遍历到3时，4是栈顶元素，所以3能量发射给4,3入栈，遍历到2,2能量给3，2入栈，遍历到1,1能量给2,1入栈，5大于1，开始向右发射，直到5把前面四个元素的能量都吸收（此时栈内元素都弹出了，5入栈）。

最后查找累积能量的数组的最大值就可。

C - Po

题目大意

有一个长度为 n 的数组。在初始状态下，所有元素都为 00。

每次操作，可以将一个连续的区间 [l,r] 内的所有数加上一个正整数 x，但要求任意两个操作区间要么互不相交，要么一个包含另外一个。

请问能将原数组变为给定数组 a 的最少操作次数。

解题思路

以123213为例，如果用图形来表示，那么就可以把这个想象成一个有起伏的山坡，之后，要想清楚一件事，这道题才有思路：这里的区间相加其实是可以进行变换的，操作[1,3],[2,5]和[1,5],[2,3]得到的结果其实是一样的。那么对于一个上坡一个下坡，两边等高的部分其实只用操作一次，这个用单调栈就可以实现。

遍历数组其实可以看做一个上下坡的过程，上坡的时候，遇到高的就入栈并计数，到山顶后，遇到矮的，就不断让栈顶数出栈，直到当前数不比栈顶数小为止，然后比较栈顶数和当前数，如果相等就continue跳过看下一个数就好了，因为前面上坡的时候在登高的位置已经计数过了。continue的过程可以看做是把当前数水平线以上的山削平，然后比较两头的数。