第51天|LeetCode503.下一个更大元素 II、LeetCode42. 接雨水

1.题目链接：下一个更大元素 II

题目描述：

                给定一个循环数组 nums （ nums[nums.length - 1] 的下一个元素是 nums[0] ），返回 nums 中每个元素的 下一个更大元素 。

                数字 x 的 下一个更大的元素 是按数组遍历顺序，这个数字之后的第一个比它更大的数，这意味着你应该循环地搜索它的下一个更大的数。如果不存在，则输出 -1 。

解法：

                其实本题的解法和裸的单调栈是一样的，不同的地方就是他是一个环型的数组。我们可以将数组长度变成两倍然后将值都求出来，最后取前三个值。也可以不用将所有的值都求出来，我们只需要将i取模操作，就可以模拟成环的过程。所以不同的地方就是，遍历从0到length×2，i变成i%length。

下面为代码（java）：

2.题目链接：42. 接雨水 

题目描述：

                给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

解法：

                ①本题有两种解法，一种双指针，一种单调栈，这里只用了双指针。

                ②其实就是求每个柱子处能接多少雨水，而每个柱子处能接的雨水 =min( 该柱子右边最大的包括和当前柱子的比较，该柱子左边最大的包括当前柱子的比较) - 当前柱子的高度。注意能接到水肯定要形成漏斗，所以长度小于等于2的时候，肯定接不到水，直接返回0.

                ③要注意的是在求右边的时候，根据的是后面的值求的，所以遍历顺序是从后到前。

                ④在求左边的时候，根据的是前面的值求的，所以遍历顺序是从前到后。

                ⑤最后将每个柱子能接的雨水求和即可。

下面为代码（java）：

3.总结：

                ①环形的单调栈问题想到取模。

                ②求雨水问题，双指针解法：min（左边最大，右边最大）- 当前高度。要注意遍历顺序。单调栈写法二刷再来。