2018-11-15 Summary lc42/84 单调栈

主要两个题目：
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等方法
阅读官方文档