問題：
給定一個陣列，想象成一個桶，問最多能裝多少水？
例【1，5，3，6】 最多裝2格水 O O ~ O O ~ O O O O O O O O O O O
解題思路：
我們把每一列當成一塊板，根據分析，第一塊板和最后一塊板一定不能蓄水，所以問題變成了所有板所能蓄水最大值的總和，先明確這個思路，之后再想辦法，
那么如何確定當前板可以蓄多少水呢？和它左右兩邊最長的板有關系，等于左右兩邊最長板的較小者減去當前板的長度和0取最大值，
表示為:
當前板蓄水量 = math.max(0, math.min(左最長板，右最長板) - 當前）
第一、最后一塊板蓄水量 = 0
方法一：O(n^2)
簡單暴力，挨個遍歷每一塊板，求出左右最大值，根據上面公式進行計算，不做演示
方法二：O(n)
根據方法一可知，時間復雜度主要在尋找每一塊板的左右最大值，那么優化的方向就是使用O(n)復雜度獲得每一塊板的左右最大值，
怎么做呢？借助輔助陣列，
例如【1，5，3，6】，則左邊最大值陣列為【1，5，5，6】，右邊最大值陣列為【6，6，6，6】
三個陣列分別表示當前板長度，當前板的左邊板最大長度、當前板的右邊板最大長度，
public static int shui(int[] param) { if(param == null || param.length < 2) return 0; int[] L = new int[param.length]; int[] R = new int[param.length]; for(int i=1;i<param.length;i++) { L[i] = Math.max(param[i], param[i - 1]); } for(int i=param.length - 2;i>0;i--) { R[i] = Math.max(param[i], param[i + 1]); } int shui = 0; for(int i = 1; i<param.length-1;i++) { shui += Math.max(0, Math.min(L[i], R[i]) - param[i]); } return shui; }
方法三：O(n)
方法二空間復雜度太大，所以還有優化空間，
可以從兩邊同時進行判斷，并且保存當前左右最大值，
如果左邊最大值小于右邊最大值，那么左邊的當前板所能蓄水量就可確定 = math.max(0, 左最大值 - 當前），并且當前索引++，標記左邊最大值 = math.max(左最大值，當前板)，
如果右邊最大值小于左邊最大值，那么右邊的當前板所能蓄水量就可確定 = math.max(0, 右最大值 - 當前），并且當前索引--，標記右邊最大值 = math.max(右最大值，當前板)，
如果相等，隨便歸屬一邊，或兩邊一起計算，
/* * 給定一個陣列，想象成一個桶，問最多能裝多少水 * 例【1，5，3，6】 最多裝2格水 * O * O ~ O * O ~ O * O O O * O O O * O O O O * */ public static int shui(int[] param) { if(param == null || param.length < 2) return 0; int L = 1, R = param.length-2, shui = 0; int lmax = param[0], rmax = param[R + 1]; while(L<=R) { if(lmax <= rmax) { shui += Math.max(0, lmax - param[L]); lmax = Math.max(lmax, param[L++]); }else { shui += Math.max(0, rmax - param[R]); rmax = Math.max(rmax, param[R--]); } } return shui; } public static void main(String[] args) { int[] a = {2,1,3,5,2,6}; System.out.println(shui(a)); }
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/270767.html
標籤：其他
上一篇：演算法 等概率問題