主要两个题目：
leetcode 42 Trapping Rain Water
lletcode 84 Largest Rectangle in Histogram
结合两个题目，学习了单调栈的基本概念和基本用法
42:自己做的方法：暴力遍历，但是要处理各种特殊情况，修改了很多次才AC
class Solution {
public int trap(int[] height) {
int res = 0;
if (height.length<3) return res;
//System.out.println("line 5");
for (int i=0;i<height.length-1;i++){
if (height[i+1]>=height[i]) continue;
int sum_i = 0;
int max_min = 0;
int max_min_j = 0;
//System.out.println("i="+i);
for (int j=i+1;j<height.length;j++){
if (height[j]>=height[i]){
for (int k=i+1;k<j;k++)
sum_i += height[i] - height[k];
//System.out.println("no. "+i+" :res+ "+sum_i);
i = j-1;
break;
}
else{
if (height[j] >= max_min){
max_min_j = j;
max_min = Math.max(max_min, height[j]);
}
}
if (j == height.length-1){
//System.out.println("no. "+i+" :max_min+ "+max_min);
for (int k=i+1;k<max_min_j;k++)
sum_i += max_min - height[k];
i = max_min_j-1;
}
}
res += sum_i;
}
return res;
}
}
基本思想是从某处开始往后找比这一处大的，找到就求这个“凹槽”的积水值。
刚开始不过的点在于：
- 如果在后面没有找到比现在大的，就要记录后面的最大值，然后求该处到max_min处的雨水数量。
- 此解法中，每求一次区间面积，就要更新i到j-1（for循环会对i+1），所以下一次从j处开始处理。
觉得这个解法实在是很蠢，但是ac结果却挺好
执行用时: 12 ms, 在Trapping Rain Water的Java提交中击败了99.55% 的用户
代码里嵌套了三层循环，很不优化了，所以对这个ac结果感觉很奇怪...
阅读了lc社区里的文章，学习到的三个方法都很有价值：
- 单调栈（递减栈）
- DP 从两头分别遍历一次，保存每个点的左右最大值
-
双指针的使用（精妙）
方法三
class Solution {
public int trap(int[] height) {
int left = 0;
int right = height.length - 1;
int result = 0;
int leftMax=0, rightMax=0;
while(left < right){
if(height[left] < height[right]){
leftMax = Math.max(height[left], leftMax);
result += leftMax - height[left];
left++;
}else{
rightMax = Math.max(height[right], rightMax);
result += rightMax - height[right];
right--;
}
}
return result;
}
}
基本思想是：左边右边设置双指针，左边小于右边，则计算左边处积水值，移动左指针；否则计算右边积水值，更新右指针。两个指针最终相遇于最大值处。
根据是：在此方法中，左指针右边有大于该处的值，则该处积水值由左边最大值决定； 右指针左边有大于该处的值，则该处积水值由右边最大值决定。
Complexity analysis
- Time complexity: O(n)O(n). Single iteration of O(n)O(n).
- Space complexity: O(1)O(1) extra space. Only constant space required for left, right, left_max and right_max.
综合考虑时间复杂度、空间复杂度，这应该是本问题的最佳解法；
单调栈是本题接触的方法，在直方图最大矩形中也用到了单调栈，但是当时没有注意这个概念。本题使用递减单调栈，而84使用递增单调栈，两个题目对比琢磨，很值得学习。
待学习：原地归并排序算法
熟悉arrays.copyOf System.arraycopy等方法
阅读官方文档
