專欄：50多種數(shù)據(jù)結(jié)構(gòu)徹底征服

專欄：50多種經(jīng)典圖論算法全部掌握

最近一網(wǎng)友在找工作的時候，收到美團的offer，而面試的其他幾家還沒開獎，所以想在等等，結(jié)果美團的offer作廢了。offer的確認(rèn)都是有時效的，給你發(fā)了你不確認(rèn)，人家以為你不打算去了。

面試之后如果手里暫時沒有offer，其他幾家還不確定的時候，可以先接了，不能太貪，如果覺得不滿意，以后還可以再跳槽。給你了你不接，萬一后面幾個都不發(fā)，豈不是一個offer都沒了，只能走社招了。

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

來看下今天的算法題，這題是LeetCode的第84題：柱狀圖中最大的矩形。

問題描述

來源：LeetCode第84題

難度：困難

給定 n 個非負(fù)整數(shù)，用來表示柱狀圖中各個柱子的高度。每個柱子彼此相鄰，且寬度為 1 。求在該柱狀圖中，能夠勾勒出來的矩形的最大面積。

示例1：

輸入：heights = [2,1,5,6,2,3] 輸出：10 解釋：最大的矩形為圖中紅色區(qū)域，面積為 10

• 1 <= heights.length <=10^5

• 0 <= heights[i] <= 10^4

問題分析

這題讓求的是柱狀圖能勾勒出來的最大矩形面積，因為勾勒出來的最大矩形面積高度肯定是其中某一個柱子的高度，我們可以使用單調(diào)棧解決，單調(diào)棧存儲的是元素的下標(biāo)， 下標(biāo)對應(yīng)的值從棧底到棧頂是單調(diào)遞增的 。

遍歷數(shù)組的時候，如果當(dāng)前元素的值大于等于棧頂元素所對應(yīng)的值，就把當(dāng)前元素的下標(biāo)添加到棧中。如下圖，當(dāng)遍歷到前4個元素的時候，因為都是后面一個比前面一個大，所以都壓棧，注意壓入的是元素下標(biāo)，不是元素的值。

如果當(dāng)前元素的值小于棧頂元素，說明棧頂元素遇到了右邊比他小的，那么這個棧頂元素左邊比他小的是哪個呢？就是它在棧中的下一個元素（也有可能相等，但不影響后面的計算），也就是棧頂元素出棧之后新的棧頂元素。

當(dāng)我們知道一個柱子左邊和右邊比他小的，就可以計算以當(dāng)前柱子為矩形高度所能勾勒出來的最大矩形了。比如上面的圖中當(dāng)指針指向 2 的時候，我們來看下計算步驟。

這里要注意一點的是數(shù)組中的第一個元素前面是沒有值的，最后一個元素后面也是沒有值的，所以我們可以把數(shù)組的前面和后面分別添加一個 0 。

JAVA：

public int largestRectangleArea(int[] heights) {     Stack
         
  stack =  new Stack<>(); // 棧頂?shù)綏５资沁f減的      // 第一個柱子的下標(biāo)是0，默認(rèn)他前面一個是-1。     stack.push(- 1);      int maxArea =  0; // 記錄最大面積      for ( int i =  0; i <= heights.length; i++) {          // 當(dāng)前柱子的高度，如果i == heights.length，表示沒有柱子，高度為0。          int curHeight = i == heights.length ?  0 : heights[i];          // 如果當(dāng)前柱子的高度小于棧頂元素所對應(yīng)柱子的高度，棧頂元素出棧，計算面積。          while (stack.size() >  1 && curHeight < heights[stack.peek()]) {              int h = heights[stack.pop()]; // 出棧的柱子高度              int area = (i -  1 - stack.peek()) * h; // 計算面積             maxArea = Math.max(maxArea, area); // 保存最大面積         }         stack.push(i); // 當(dāng)前柱子的下標(biāo)入棧     }      return maxArea; // 返回最大面積。 }

C++：

public:     int largestRectangleArea(vector

  &heights) {         stack

  stk;// 棧頂?shù)綏５资沁f減的         // 第一個柱子的下標(biāo)是0，默認(rèn)他前面一個是-1。         stk.push(-1);         int maxArea = 0;// 記錄最大面積         for (int i = 0; i <= heights.size(); i++) {             // 當(dāng)前柱子的高度，如果i == heights.length，表示沒有柱子，高度為0。             int curHeight = i == heights.size() ? 0 : heights[i];             // 如果當(dāng)前柱子的高度小于棧頂元素所對應(yīng)柱子的高度，棧頂元素出棧，計算面積。             while (stk.size() > 1 && curHeight < heights[stk.top()]) {                 int h = heights[stk.top()];// 出棧的柱子高度                 stk.pop();                 int area = (i - 1 - stk.top()) * h;// 計算面積                 maxArea = max(maxArea, area);// 保存最大面積             }             stk.push(i);// 當(dāng)前柱子的下標(biāo)入棧         }         return maxArea;// 返回最大面積。     }

Python：

    def largestRectangleArea(self, heights: List[int]) -> int:         # 第一個柱子的下標(biāo)是0，默認(rèn)他前面一個是 - 1。         stk = [-1]  # 棧頂?shù)綏５资沁f減的         maxArea = 0  # 記錄最大面積         for i in range(0, len(heights) + 1):             # 當(dāng)前柱子的高度，如果i == heights.length，表示沒有柱子，高度為0。             curHeight = 0 if i == len(heights) else heights[i]             # 如果當(dāng)前柱子的高度小于棧頂元素所對應(yīng)柱子的高度，棧頂元素出棧，計算面積。             while len(stk) > 1 and curHeight < heights[stk[-1]]:                 h = heights[stk.pop()]  # 出棧的柱子高度                 area = (i - 1 - stk[-1]) * h  # 計算面積                 maxArea = max(maxArea, area)  # 保存最大面積             stk.append(i)  # 當(dāng)前柱子的下標(biāo)入棧         return maxArea  # 返回最大面積。

筆者簡介

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