主要兩個題目：
leetcode 42 Trapping Rain Water
lletcode 84 Largest Rectangle in Histogram
結(jié)合兩個題目，學(xué)習(xí)了單調(diào)棧的基本概念和基本用法

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;
    }
}

基本思想是從某處開始往后找比這一處大的，找到就求這個“凹槽”的積水值。

剛開始不過的點在于：

• 如果在后面沒有找到比現(xiàn)在大的，就要記錄后面的最大值，然后求該處到max_min處的雨水數(shù)量。
• 此解法中，每求一次區(qū)間面積，就要更新i到j(luò)-1（for循環(huán)會對i+1），所以下一次從j處開始處理。

覺得這個解法實在是很蠢，但是ac結(jié)果卻挺好

執(zhí)行用時: 12 ms, 在Trapping Rain Water的Java提交中擊敗了99.55% 的用戶

代碼里嵌套了三層循環(huán)，很不優(yōu)化了，所以對這個ac結(jié)果感覺很奇怪...

閱讀了lc社區(qū)里的文章，學(xué)習(xí)到的三個方法都很有價值：

• 單調(diào)棧（遞減棧）
• 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;
}
}

基本思想是：左邊右邊設(shè)置雙指針，左邊小于右邊，則計算左邊處積水值，移動左指針；否則計算右邊積水值，更新右指針。兩個指針最終相遇于最大值處。
根據(jù)是：在此方法中，左指針右邊有大于該處的值，則該處積水值由左邊最大值決定； 右指針左邊有大于該處的值，則該處積水值由右邊最大值決定。

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.

綜合考慮時間復(fù)雜度、空間復(fù)雜度，這應(yīng)該是本問題的最佳解法；

單調(diào)棧是本題接觸的方法，在直方圖最大矩形中也用到了單調(diào)棧，但是當時沒有注意這個概念。本題使用遞減單調(diào)棧，而84使用遞增單調(diào)棧，兩個題目對比琢磨，很值得學(xué)習(xí)。

待學(xué)習(xí)：原地歸并排序算法
熟悉arrays.copyOf System.arraycopy等方法
閱讀官方文檔