阿里P8跪在了這道題上。。。
本文轉(zhuǎn)載自微信公眾號(hào)「高性能架構(gòu)探索」，作者雨樂(lè)。轉(zhuǎn)載本文請(qǐng)聯(lián)系高性能架構(gòu)探索公眾號(hào)。
今年，北京的雨尤其多，淅淅瀝瀝的。整個(gè)中秋節(jié)前兩天，都是在雨中度過(guò)，沒(méi)了往日中秋節(jié)的快樂(lè)氣氛，幸運(yùn)的是，在中秋節(jié)當(dāng)天，天氣晴朗，算是對(duì)整個(gè)假期畫(huà)上了個(gè)還算滿意的句號(hào)。
聽(tīng)著淅淅瀝瀝的雨聲，想起前段時(shí)間在脈脈上看了一篇帖子，阿里P8去面試某條，掛在了一面算法上。而自己在3年前面試某公司，也栽在了同樣的一道算法上。正所謂吃一塹長(zhǎng)一智，把該算法題重新整理了下，分享給大家，希望能夠有用。
接雨水
給定 n 個(gè)非負(fù)整數(shù)表示每個(gè)寬度為 1 的柱子的高度圖，計(jì)算按此排列的柱子，下雨之后能接多少雨水。
接雨水
輸入：height = [0,1,0,2,1,0,1,3,2,1,2,1] 輸出：6
解釋：上面是由數(shù)組[0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度圖，在這種情況下，可以接6個(gè)單位的雨水(藍(lán)色部分表示雨水)
看到題目的第一眼，感覺(jué)很簡(jiǎn)單，但是卻不知道從何入手。下面我們將遵循循序漸進(jìn)的方式，分析此題目的解法。
暴力解法
看到題目的一刻，出于思維定式，必定去查找"凹"型槽的最低部分，然后。。。，如此如此，越來(lái)越頭大，直至放棄。
我們不妨換個(gè)思路，每根柱子上能放多少雨水。那么每根柱子上盛放雨水的高度怎么計(jì)算呢?就是其左右兩邊柱子最大高度的較小者與其高度之差，文字上理解起來(lái)比較費(fèi)力，用圖的方式更加便于大家理解。
下面我們將計(jì)算柱子坐標(biāo)(3)-(7)即紅框內(nèi)的盛水量。
我們首先定義4個(gè)變量:
- res 盛水總量，其初始化為0
- height 當(dāng)前柱子高度
- left_max 左邊最大高度(包括當(dāng)前柱子本身
- right_max 右邊最大高度(包括其本身)
首先，計(jì)算柱子(3)處其盛水量。其左邊最大高度left_max為2，右邊最大高度right_max為3，那么橫坐標(biāo)3處盛水量為min(left_max, right_max) - height 賦值之后為min(2, 3) - 2，答案為0，也就是說(shuō)柱子(3)可盛水量為0。
接著我們計(jì)算柱子(4)處盛水量。按照上述計(jì)算規(guī)則，左邊最大高度為2，右邊最大高度為3，那么柱子(4)可盛水量為min(2, 3)- 1，答案為1。
然后計(jì)算柱子(5)處的盛水量，按照上述計(jì)算規(guī)則，左邊最大高度為2，右邊最大高度為3，那么柱子(5)可盛水量為min(2, 3)- 0，答案為2。
然后計(jì)算柱子(6)處的盛水量，按照上述計(jì)算規(guī)則，左邊最大高度為2，右邊最大高度為3，那么柱子(6)可盛水量為min(2, 3)- 1，答案為1。
最后計(jì)算柱子(7)處的盛水量，左邊最大高度為3，右邊最大高度為3，那么柱子(7)可盛水量為min(3, 3) - 3即0.
因此，柱子(3)到柱子(7)之間所盛水量res = 0 + 1 + 2 + 1 + 0 = 4.
代碼實(shí)現(xiàn)一：
- int trap(vector<int>& height) {
- int res = 0;
- for (int cur = 0; cur < height.size(); ++cur) {
- int left_max = 0;
- int right_max = 0;
- // 計(jì)算左邊最大高度
- for (int left = 0; left <= cur; ++left) {
- left_max = std::max(left_max, height[left]);
- }
- // 計(jì)算右邊最大高度
- for (int right = cur; right < height.size(); ++right) {
- right_max = std::max(right_max, height[right]);
- }
- // 計(jì)算總盛水量
- res += std::min(left_max, right_max) - height[cur];
- }
- return res;
- }
上述規(guī)則有個(gè)trick，就是計(jì)算兩邊最高的時(shí)候，都將柱子本身的高度計(jì)算在內(nèi)，這樣做是為了在計(jì)算盛水量的時(shí)候，方便計(jì)算。
假設(shè)計(jì)算柱子(3)，如果在計(jì)算兩邊最大高度的時(shí)候不包括柱子(3)本身的高度，那么柱子(3)左邊最大高度為1，右邊最大高度為3，在計(jì)算盛水量的時(shí)候，就需要判min(lext_max, right_max)與柱子(3)本身的大小，否則會(huì)出現(xiàn)負(fù)值，代碼實(shí)現(xiàn)如下。
代碼實(shí)現(xiàn)二
- int trap(vector<int>& height) {
- int res = 0;
- for (int cur = 0; cur < height.size(); ++cur) {
- int left_max = 0;
- int right_max = 0;
- // 計(jì)算左邊最大高度
- // 注意，與實(shí)現(xiàn)一相比，left到cur的前一個(gè)截止
- for (int left = 0; left < cur; ++left) {
- left_max = std::max(left_max, height[left]);
- }
- // 計(jì)算右邊最大高度
- // 注意，與實(shí)現(xiàn)一相比，right從下一個(gè)開(kāi)始
- for (int right = cur + 1; right < height.size(); ++right) {
- right_max = std::max(right_max, height[right]);
- }
- // 計(jì)算總盛水量
- int mx = std::min(left_max, right_max);
- if (mx > height[cur]) { // 需要進(jìn)行判斷
- res += mx - height[cur];
- }
- }
- return res;
- }
暴力解法，理解起來(lái)簡(jiǎn)單，時(shí)間復(fù)雜度為O(n2),提交之后，毫無(wú)疑問(wèn)會(huì)TLE，下面我們從其他方面對(duì)暴力法進(jìn)行優(yōu)化。
為了便于理解，后面的實(shí)現(xiàn)將使用實(shí)現(xiàn)二的思想。
動(dòng)態(tài)規(guī)劃
看了暴力法的實(shí)現(xiàn)，我們基本思路已經(jīng)有了，其時(shí)間復(fù)雜度為O(n2)，時(shí)間主要消耗在查找兩邊最大柱子高度上。那么有沒(méi)有什么辦法，能夠 常數(shù)次 遍歷就能獲取到所有柱子的兩邊高度呢?
我們?nèi)匀灰?/p>
- height = [0,1,0,2,1,0,1,3,2,1,2,1]
為例，計(jì)算雙邊最大值。
左側(cè)最大值
定義數(shù)組left_max，其中l(wèi)eft_max[i]代碼第i個(gè)柱子左邊最大高度。
下面我們來(lái)計(jì)算柱子左側(cè)的最大高度：
- 柱子(0)，左側(cè)最大高度為0(其左側(cè)沒(méi)有柱子)
- 柱子(1)，左側(cè)最大高度為0(左側(cè)只有柱子0)
- 柱子(2)，左側(cè)最大高度為1([0 1]數(shù)組的最大值)
- 柱子(3)，左側(cè)最大高度為1([0 1 0]數(shù)組最大值)
- 柱子(4)，左側(cè)最大高度為2([0 1 0 2]數(shù)組最大值)
- 柱子(5)，左側(cè)最大高度為2([0 1 0 2 1]數(shù)組最大值)
- 柱子(6)，左側(cè)最大高度為2([0 1 0 2 1 0]數(shù)組最大值)
- 柱子(7)，左側(cè)最大高度為2([0 1 0 2 1 0 1]數(shù)組最大值)
- 柱子(8)，左側(cè)最大高度為3([0 1 0 2 1 0 1 3]數(shù)組最大值)
- 柱子(9)，左側(cè)最大高度為3([0 1 0 2 1 0 1 3 2]數(shù)組最大值)
- 柱子(10)，左側(cè)最大高度為3([0 1 0 2 1 0 1 3 2 1]數(shù)組最大值)
- 柱子(11)，左側(cè)最大高度為3([0 1 0 2 1 0 1 3 2 1 2]數(shù)組最大值)
左側(cè)最大值
從上述規(guī)則，我們進(jìn)行分析，發(fā)現(xiàn)有一定的規(guī)律可循，即當(dāng)前柱子左側(cè)最大高度 為 max(上一個(gè)柱子左側(cè)最大高度, 上一個(gè)柱子高度)。
代碼表示如下:
- std::vector<int> left_max(height.size(), 0);
- for (int i = 1; i < height.size(); ++i) {
- left_max[i] = std::max(left_max[i - 1], height[i]);
- }
對(duì)上述代碼進(jìn)行稍許變化后如下：
- std::vector<int> left_max(height.size(), 0);
- int mx = 0;
- for (int i = 0; i < height.size(); ++i) {
- left_max[i] = mx;
- mx = std::max(mx, height[i]);
- }
右側(cè)最大值
定義數(shù)組right_max，其中l(wèi)eft_max[i]代碼第i個(gè)柱子右邊最大高度。
因?yàn)橐?jì)算右側(cè)最大值，所以必須從最后一個(gè)開(kāi)始向前計(jì)算(如果從第一個(gè)開(kāi)始計(jì)算的，那么跟暴力法沒(méi)區(qū)別了)。height = [0,1,0,2,1,0,1,3,2,1,2,1]
- 柱子(11)，右側(cè)最大高度為0(其右側(cè)沒(méi)有柱子)
- 柱子(10)，右側(cè)最大高度為1([1]的最大值)
- 柱子(9)，右側(cè)最大高度為2([2 1]的最大值)
- 柱子(8)，右側(cè)最大高度為2([1 2 1]的最大值)
- 柱子(7)，右側(cè)最大高度為2([2 1 2 1]的最大值)
- 柱子(6)，右側(cè)最大高度為3([3 2 1 2 1]的最大值)
- 柱子(5)，右側(cè)最大高度為3([1 3 2 1 2 1]的最大值)
- 柱子(4)，右側(cè)最大高度為3([0 1 3 2 1 2 1]的最大值)
- 柱子(3)，右側(cè)最大高度為3([1 0 1 3 2 1 2 1]的最大值)
- 柱子(2)，右側(cè)最大高度為3([2 1 0 1 3 2 1 2 1]的最大值)
- 柱子(1)，右側(cè)最大高度為3([0 2 1 0 1 3 2 1 2 1]的最大值)
- 柱子(0)，右側(cè)最大高度為3([1 0 2 1 0 1 3 2 1 2 1]的最大值)
右側(cè)最大值
既然計(jì)算出來(lái)了雙邊最大值，那么我們來(lái)實(shí)現(xiàn)下代碼：
- int trap(vector<int>& height) {
- int res = 0;
- std::vector<int> left_max(height.size());
- std::vector<int> right_max(height.size());
- int mx = 0;
- // 循環(huán)一、計(jì)算左側(cè)最大值
- for (int i = 0; i < height.size(); ++i) {
- left_max[i] = mx;
- mx = std::max(mx, height[i]);
- }
- mx = 0;
- // 循環(huán)二、計(jì)算右側(cè)最大值
- for (int i = height.size() - 1; i >= 0; --i) {
- right_max[i] = mx;
- mx = std::max(mx, height[i]);
- }
- // 循環(huán)三、計(jì)算所盛雨水量
- for (int i = 0; i < height.size(); ++i) {
- int mn = std::min(left_max[i], right_max[i]);
- if (mn > height[i]) {
- res += mn - height[i];
- }
- }
- return res;
- }
上述代碼較暴力方法優(yōu)化后，時(shí)間復(fù)雜度優(yōu)化為O(n), 提交后AE。
動(dòng)態(tài)規(guī)劃
上述代碼中有3個(gè)循環(huán)，空間復(fù)雜度為O(2n)，又作為c++ coder這是不能忍的，能不能再進(jìn)行優(yōu)化呢?我們看到循環(huán)三單純?yōu)橛?jì)算盛雨量，能否將循環(huán)二和循環(huán)3合并，并且優(yōu)化空間復(fù)雜度呢?必須可以，為了閱讀起來(lái)方便，我們實(shí)現(xiàn)代碼如下：
- int trap(vector<int>& height) {
- int res = 0;
- std::vector<int> v(height.size());
- int mx = 0;
- // 循環(huán)一、計(jì)算左側(cè)最大值
- for (int i = 0; i < height.size(); ++i) {
- v[i] = mx;
- mx = std::max(mx, height[i]);
- }
- mx = 0;
- // 循環(huán)二、計(jì)算右側(cè)最大值 并 計(jì)算盛水量
- for (int i = height.size() - 1; i >= 0; --i) {
- int mn = std::min(mx, v[i]);
- mx = std::max(mx, height[i]);
- if (mn > height[i]) {
- res += mn - height[i];
- }
- }
- return res;
- }
優(yōu)化后的動(dòng)態(tài)規(guī)劃
雙指針
動(dòng)態(tài)規(guī)劃方法，時(shí)間復(fù)雜度和空間復(fù)雜度都是O(n)，下面我們介紹一種只有一次循環(huán)且空間復(fù)雜度為O(1)的算法，這就是雙指針?biāo)惴ā?/p>
接雨水算法的核心思想，就是計(jì)算當(dāng)前柱子的盛水量，也就是左右兩邊的最大值的較小者與當(dāng)前柱子之差。我們先求出數(shù)組雙端柱子的較小值，然后兩邊柱子跟這個(gè)較小值相比較，如果較小值為左邊的柱子，則左邊柱子向右移動(dòng)，直至比當(dāng)前較小值大。反之，如果較小值為右側(cè)柱子，則右側(cè)柱子向左移動(dòng)，直至比當(dāng)前值大。
left 和 right 兩個(gè)指針?lè)謩e指向數(shù)組的首尾位置，從兩邊向中間掃描，在當(dāng)前兩指針確定的范圍內(nèi)，先比較兩頭找出較小值，如果較小值是 left 指向的值，則從左向右掃描，如果較小值是 right 指向的值，則從右向左掃描，若遇到的值比當(dāng)較小值小，則將差值存入結(jié)果，如遇到的值大，則重新確定新的窗口范圍，以此類推直至 left 和 right 指針重合
- int trap(vector<int>& height) {
- int res = 0;
- int left = 0;
- int right = height.size() - 1;
- while (left < right) {
- int mn = min(height[left], height[right]);
- if (mn == height[left]) {
- ++left;
- while (left < right && height[left] < mn) {
- res += mn - height[left++];
- }
- } else {
- --right;
- while (left < right && height[right] < mn) {
- res += mn - height[right--];
- }
- }
- }
- return res;
- }
單調(diào)棧
此種方法較前面的兩種(暴力法和雙指針?lè)?，如果說(shuō)前面兩種方法都是求每根柱子上盛水量之和的話(即 按列計(jì)算)，那么單調(diào)棧方法則是 按行計(jì)算 每一層的盛水量，如下圖所示：
逐層計(jì)算
每一行水左右肯定都會(huì)被柱子卡住。那么從左向右遍歷柱子，如果高度在下降，那么顯然不會(huì)蓄水。如果高度上升了，那就說(shuō)明中間是個(gè)低點(diǎn)，這之間可以蓄水。而這個(gè)下降的高度用單調(diào)棧來(lái)維護(hù)就行了，棧里我們只放下標(biāo)。
遍歷高度，如果此時(shí)棧為空，或者當(dāng)前高度小于等于棧頂高度，則把當(dāng)前高度的坐標(biāo)壓入棧，注意這里不直接把高度壓入棧，而是把坐標(biāo)壓入棧，這樣方便在后來(lái)算水平距離。當(dāng)遇到比棧頂高度大的時(shí)候，就說(shuō)明有可能會(huì)有坑存在，可以裝雨水。此時(shí)棧里至少有一個(gè)高度，如果只有一個(gè)的話，那么不能形成坑，直接跳過(guò)，如果多余一個(gè)的話，那么此時(shí)把棧頂元素取出來(lái)當(dāng)作坑，新的棧頂元素就是左邊界，當(dāng)前高度是右邊界，只要取二者較小的，減去坑的高度，長(zhǎng)度就是右邊界坐標(biāo)減去左邊界坐標(biāo)再減1，二者相乘就是盛水量。
我們?nèi)匀灰詳?shù)組height = [0,1,0,2,1,0,1,3,2,1,2,1]為例來(lái)說(shuō)明單調(diào)棧的用法。
假設(shè)res初始值為0，用其來(lái)計(jì)算height數(shù)組所表示的柱子高度最大盛水量。
- 初始化時(shí)候，棧為空。
棧為空
- 因?yàn)闂榭眨韵聵?biāo)0入棧，如下圖所示：
- 由于下標(biāo)1所指向的數(shù)組height[1] = 1大于棧頂下標(biāo)所指向的數(shù)，所以下標(biāo)0出棧，下標(biāo)1入棧。
- 由于下標(biāo)2指向的值小于棧頂值，則下標(biāo)2入棧。
此時(shí)下標(biāo)指向3，由于下標(biāo)3指向的值大于棧頂下標(biāo)指向的值，則出棧，計(jì)算增量盛水量((min(2, 1) - 0) * (3 - 1 - 1) = 1)，即增量為1，此時(shí)res = 1。
- 由于下標(biāo)1所指向的高度小于下標(biāo)3指向高度，則下標(biāo)1出棧，此時(shí)棧為空，則下標(biāo)3進(jìn)棧。
- 下標(biāo)4指向的值小于棧頂下標(biāo)指向的值(1 < 2),下標(biāo)4入棧
- 下標(biāo)5指向的值小于棧頂下標(biāo)指向的值(0 < 1),下標(biāo)5入棧
- 此時(shí)下標(biāo)6指向的值為1，大于棧頂下標(biāo)所指向的值(1 > 0)，則執(zhí)行出棧，同時(shí)計(jì)算盛水增量((min(1, 1) - 0) * (6 - 4 - 1)),增量為1，此時(shí)res = 1 + 1 = 2。
- 下標(biāo)6所指向的值等于棧頂指向的值(1 = 1),下標(biāo)6入棧
- 此時(shí)下標(biāo)指向7，其值大于棧頂值(3 > 1)，則棧頂出棧，計(jì)算增量為((min(3, 1) - 1) * (7 - 4 - 1)),增量為0，此時(shí)res = 1 + 1 + 0 = 2
- 此時(shí)，下標(biāo)仍為7，棧頂值為4，由于當(dāng)前下標(biāo)指向值大于棧頂指向值，則出棧，計(jì)算盛水增量((min(3, 2) - 1) * (7 - 3 - 1)),增量為3，此時(shí)res = 1 + 1 + 0 + 3 = 5
計(jì)算增量盛水量
- 此時(shí)棧內(nèi)只有下標(biāo)3，且其所指向值小于當(dāng)前下標(biāo)指向值(2 < 3)，則出棧
下標(biāo)3出棧
此時(shí)棧為空，則下標(biāo)7入棧
- 下標(biāo)8指向值小于棧頂指向值(2 < 3),下標(biāo)8入棧
- 下標(biāo)9指向值小于棧頂指向值(1 < 2),下標(biāo)9入棧
- 此時(shí)下標(biāo)為10，其對(duì)應(yīng)值大于棧頂指向值(2 > 1)，則棧頂出棧，并計(jì)算增量((min(2, 2) - 1) * (10 - 8 - 1)),增量為1，此時(shí)res = 1 + 1 + 0 + 3 + 1 = 6
- 下標(biāo)10指向值小于棧頂值，入棧
下標(biāo)11指向值小于棧頂值，入棧
此時(shí)，數(shù)組循環(huán)結(jié)束，盡管棧內(nèi)還有數(shù)，坐標(biāo)為7 8 10 11，指向的值為3 2 2 1，但其已經(jīng)不能構(gòu)成一個(gè)凹槽進(jìn)行盛水，所以算法執(zhí)行結(jié)束。
代碼實(shí)現(xiàn)如下：
- int trap(vector<int>& height) {
- stack<int> st;
- int i = 0, res = 0, n = height.size();
- while (i < n) {
- if (st.empty() || height[i] <= height[st.top()]) {
- st.push(i++);
- } else {
- int t = st.top(); st.pop();
- if (st.empty()) continue;
- res += (min(height[i], height[st.top()]) - height[t]) * (i - st.top() - 1);
- }
- }
- return res;
- }
寫(xiě)在最后
架構(gòu)或者底層原理分析方面，需要調(diào)研大量的資料，研究分析源碼，很耗費(fèi)精力。所以后面的文章中，可能會(huì)有算法(leetcode經(jīng)典算法)、面試(針對(duì)面試中遇到的一些經(jīng)典問(wèn)題)以及架構(gòu)和底層穿插發(fā)表。
