51nod，1437，迈克步，单调栈，办公软件零基础教学教材

题目描述：

题目中给出了一个长度为 $n$ 的数组 $a$，以及三个参数 $x$、$y$、$z$，每次可以将数组中的一个元素 $a_i$ 更新为 $a_i\pm x$、$a_i\pm y$ 或 $a_i\pm z$，问最少需要多少次操作才能把数组变为单调不降序列。

一个比较直观的思路是模拟每一次更新操作，然后逐个判断这个序列是否单调不降。但是这样的时间复杂度太高了，无法通过这个问题。因此我们需要寻找一种更加高效的解决方法。

我们可以发现，如果把一个单调不降的序列逆序更新，那么得到的序列仍然是单调不降的，而且每个位置上的数都不会大于此位置上原来的数。这启示我们可以采用贪心的思想，即尽可能把每个位置变小，直到它变为大于或等于此位置上的前一个数字为止，这样显然是最优的变换方案。

具体来说，我们可以使用单调栈来记录当前还未处理的数字，从左到右遍历。对于当前位置，我们从单调栈中不断弹出比它大的数字，并且对每个弹出的数字都尝试更新，更新完成后再把它插入单调栈中。

为什么要这样做呢？考虑栈中某个位置的数字 $a_i$，如果下一个数字 $a_{i+1}$ 小于它，那么 $a_i$ 必然会尝试更新，否则它们本来就可以按序排列。更新后的 $a_i$ 可能会大于此位置的前一个数字，但它必然不会大于前面的数字，因为前面的数字要么已经被更新过，要么比 $a_i$ 更小。因此我们处理的结果是最优解。算法的时间复杂度为 $O(n)$。

值得注意的一点是，题目中更新数组元素的操作有 $6$ 种，但是每种都可以转化成另一种，因此实际只需要考虑其中 $3$ 种操作：$x$、$y$ 和 $z$ 的加法，用绝对值来处理减法的情况即可。