java 单调队列，单调队列滑动窗口

一些java 单调队列和单调队列滑动窗口这样的话题，想必很多人想知道的，接下来小编带你了解一下。

给定n个非负整数，代表宽度为1的每根柱子的高度图，计算这样排列的柱子在下雨后可以接收多少雨水。上面是一个由数组[0,1,0,2,1,0,1,3,2,1,2,1]表示的高度图，在本例中是6个单位的雨水。感谢Marcos贡献了这个数字。示例输入[0,1,0,2,1,0,1,3,2,1,2,1]输出6

我们用l[i]表示第i列左侧最高列的高度，用r[i]表示其右侧最高列的高度。那么，第i列的储水量为mingt;=h[i]？min-h[i]:0。然后，要找到一个序列的最左边最大值和最右边最大值，我们遇到了很多不同的算法题。这是一个常见的算法例程。我们可以从左到右枚举，使用Push例程找到l[i]，同理从右到左找到r[i]。这些都可以在On的算法复杂度中得到解决。

然而我昨天做这道题的时候并没有想到这种解法。对于一个常年看题的人来说，看到这样的题，自然想到的解决办法就是单调题。我们可以沿着最高点将这个图分成两部分。当它充满水时，必然会变成梯子形状。因此，我们只需要找到这个阶梯形状的拐点即可。即先找到最高点，再找到第二高点，最后找到第三高点。

按照上面的思路，我们先找到最高点，然后逐渐找到梯子的角点。这里有两种算法。第一个是先排序。我们首先按照高度排序。我们用tmp来记录前一个高点的位置。如果当前高度的坐标大于前一个高点，则不予考虑，直接丢弃，否则，说明前一个高点到当前点的最大储水高度为h[i]，通过遍历计算出最终的储水量。

另一种方法是找到所有步骤的拐点。由于它是阶梯的形状，我们可以维护一个单调堆栈来解决它。什么是单调栈？即从栈底到栈顶的值的大小是单调递增或递减的。维护单调栈的方法很简单，就是当当前值小于栈顶时，直接压入栈中。当大于栈顶时，不断将栈顶弹出，直到栈为空或者小于栈顶元素。非常相似，也存在单调队列。稍后有机会我们会继续聊。

当然，这个题有很多种不同的处理方法，甚至可以不用找到最高点就用栈来解决。不过，我认为以上两种方法是最直观、最容易理解的。不知道大家有没有其他不同的解决方案，一起交流，共同进步。

关于java 单调队列和单调队列滑动窗口这类话题的讲解到这儿了，如果对诸位有所帮助，请持续关注并收藏本站。