主要兩個(gè)題目：
leetcode 42 Trapping Rain Water
lletcode 84 Largest Rectangle in Histogram
結(jié)合兩個(gè)題目尿褪，學(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;
}
}
基本思想是從某處開始往后找比這一處大的瞧毙，找到就求這個(gè)“凹槽”的積水值。
剛開始不過的點(diǎn)在于：
- 如果在后面沒有找到比現(xiàn)在大的，就要記錄后面的最大值宙彪，然后求該處到max_min處的雨水?dāng)?shù)量矩动。
- 此解法中，每求一次區(qū)間面積您访，就要更新i到j(luò)-1（for循環(huán)會(huì)對(duì)i+1）铅忿，所以下一次從j處開始處理。
覺得這個(gè)解法實(shí)在是很蠢灵汪，但是ac結(jié)果卻挺好
執(zhí)行用時(shí): 12 ms, 在Trapping Rain Water的Java提交中擊敗了99.55% 的用戶
代碼里嵌套了三層循環(huán)檀训，很不優(yōu)化了，所以對(duì)這個(gè)ac結(jié)果感覺很奇怪...
閱讀了lc社區(qū)里的文章享言，學(xué)習(xí)到的三個(gè)方法都很有價(jià)值：
- 單調(diào)棧（遞減棧）
- DP 從兩頭分別遍歷一次峻凫，保存每個(gè)點(diǎn)的左右最大值
-
雙指針的使用（精妙）
方法三
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ì)算左邊處積水值荧琼，移動(dòng)左指針；否則計(jì)算右邊積水值差牛，更新右指針命锄。兩個(gè)指針最終相遇于最大值處。
根據(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.
綜合考慮時(shí)間復(fù)雜度、空間復(fù)雜度韵卤，這應(yīng)該是本問題的最佳解法骗污；
單調(diào)棧是本題接觸的方法，在直方圖最大矩形中也用到了單調(diào)棧沈条，但是當(dāng)時(shí)沒有注意這個(gè)概念需忿。本題使用遞減單調(diào)棧，而84使用遞增單調(diào)棧拍鲤，兩個(gè)題目對(duì)比琢磨贴谎，很值得學(xué)習(xí)。
待學(xué)習(xí)：原地歸并排序算法
熟悉arrays.copyOf System.arraycopy等方法
閱讀官方文檔
