專欄：50多種數據結構徹底征服

專欄：50多種經典圖論算法全部掌握

最近在脈脈上看到一張圖片，列舉了互聯網大廠薪資的分布情況，整體來看，多數企業員工薪資集中在 20 - 50K 的區間。其中貝殼在 30 - 50K 薪資段占比最高，為 72.1% ；區間50K以上的，字節和拼多多占比最多，都是5.4%，不過我覺得這種統計比較保守了，應該沒有算上加班工資，否則只會更高。

--------------下面是今天的算法題--------------

來看下今天的算法題，這題是LeetCode的第42題：接雨水。

問題描述

來源：LeetCode第42題

難度：困難

給定 n 個非負整數表示每個寬度為 1 的柱子的高度圖，計算按此排列的柱子，下雨之后能接多少雨水。

示例1：

輸入：height = [0,1,0,2,1,0,1,3,2,1,2,1] 輸出：6 解釋：上面是由數組 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度圖，在這種情況下，可以接 6 個單位的雨水（藍色部分表示雨水）。

示例2：

輸入：height = [4,2,0,3,2,5] 輸出：9

• n == height.length

• 1 <= n <= 2 * 1^04

• 0 <= height[i] <= 10^5

問題分析

關于接雨水問題我們前面都講過，有興趣的可以先看下：

這里再來講一遍，不過今天的解決方式和之前的不一樣，今天使用的是 單調棧 來解決。

如果要計算某個位置是否能接雨水，需要找到這個位置左邊和右邊有沒有比他高的柱子，如果有，那么該位置肯定是能接的。所以我們可以使用一個單調棧，從 棧頂到棧底是單調遞增的 。

遍歷整個數組，如果數組中的某個元素比棧頂元素m大，說明棧頂元素m遇到了右邊比他大的值，這個時候棧頂元素m出棧，出棧之后如果棧不為空，那么新的棧頂元素就是左邊比他大的值，既然找到左邊和右邊都比他大的值，就可以計算位置m所能容納的水了。

注意這里計算某個位置所容納的水量不是最終的水量，如下圖中，c 位置最終容納的水是 2 ，但我們計算的時候 c 的左邊和右邊比他大的分別是 b 和 d ，他們的最小高度是 1 ，所以容納的水也是 1 。

當計算 d 的時候，左右兩邊比他大（相等也可以）的是 b 和 e ，因為 d 和 b 的高度一樣，所以計算容納水量為 0 。計算 b 的時候，他的左右兩邊比他大的分別是 a 和 e ，寬度是 3 ，高度是 1 ，容納的水量是 3 。

JAVA：

public int trap(int[] height) {     int water = 0;// 容納的水量     // 單調棧，存放的是柱子的下標，從棧頂到棧底是遞增的。     Stack
         
         
  stk =  new Stack<>();      for ( int i =  0; i < height.length; i++) {          // 如果棧不為空，并且當前元素比棧頂元素大          while (!stk.isEmpty() && height[i] > height[stk.peek()]) {              int index = stk.pop(); // 棧頂元素出棧。              // 因為棧從頂到底是遞增的，此時如果棧不為空，說明在數組中index左邊還有比他高的柱子。              if (!stk.isEmpty()) {                  int left = stk.peek(); // 左邊界                  int w = i - left -  1; // 寬度                  int h = Math.min(height[left], height[i]) - height[index];                 water += w * h; // 存數量累加             }         }         stk.push(i);     }      return water; }

C++：

public:     int trap(vector

  &height) {         int water = 0;// 容納的水量         // 單調棧，存放的是柱子的下標，從棧頂到棧底是遞增的。         stack

  stk;         for (int i = 0; i < height.size(); i++) {             // 如果棧不為空，并且當前元素比棧頂元素大             while (!stk.empty() && height[i] > height[stk.top()]) {                 int index = stk.top();                 stk.pop();// 棧頂元素出棧。                 // 因為棧從頂到底是遞增的，此時如果棧不為空，說明在數組中index左邊還有比他高的柱子。                 if (!stk.empty()) {                     int left = stk.top();// 左邊界                     int w = i - left - 1;// 寬度                     int h = min(height[left], height[i]) - height[index];                     water += w * h;// 存數量累加                 }             }             stk.push(i);         }         return water;     }

C：

#define min(a, b) (((a) < (b)) ? (a) : (b)) int trap(int *height, int heightSize) {     int water = 0;// 容納的水量     // 單調棧，存放的是柱子的下標，從棧頂到棧底是遞增的。     int *stk = malloc(20000 * sizeof(int));     int top = 0;// 棧頂     for (int i = 0; i < heightSize; i++) {         // 如果棧不為空，并且當前元素比棧頂元素大         while (top != 0 && height[i] > height[stk[top - 1]]) {             int index = stk[--top];// 棧頂元素出棧。             // 因為棧從頂到底是遞增的，此時如果棧不為空，說明在數組中index左邊還有比他高的柱子。             if (top != 0) {                 int left = stk[top - 1];// 左邊界                 int w = i - left - 1;// 寬度                 int h = min(height[left], height[i]) - height[index];                 water += w * h;// 存數量累加             }         }         stk[top++] = i;     }     return water; }

Python：

def trap(self, height: List[int]) -> int:     water = 0  # 容納的水量     # 單調棧，存放的是柱子的下標，從棧頂到棧底是遞增的。     stk = []     for i, num in enumerate(height):         # 如果棧不為空，并且當前元素比棧頂元素大         while stk and num > height[stk[-1]]:             index = stk.pop()  # 棧頂元素出棧。             # 因為棧從頂到底是遞增的，此時如果棧不為空，說明在數組中index左邊還有比他高的柱子。             if stk:                 left = stk[-1]  # 左邊界                 w = i - left - 1  # 寬度                 h = min(height[left], num) - height[index]                 water += w * h  # 存數量累加         stk.append(i)     return water

筆者簡介

博哥，真名：王一博，畢業十多年， 作者，專注于 數據結構和算法 的講解，在全球30多個算法網站中累計做題2000多道，在公眾號中寫算法題解800多題，對算法題有自己獨特的解題思路和解題技巧，喜歡的可以給個關注，也可以 下載我整理的1000多頁的PDF算法文檔 。