怎么想到要用單調(diào)棧的？
這類題目的數(shù)據(jù)通常是一維數(shù)組，要尋找任一個元素的右邊或者左邊第一個比自己大或者小的元素的位置（尋找邊界），此時我們就要想到可以用單調(diào)棧了。
?文章來源：http://www.zghlxwxcb.cn/news/detail-691870.html
42.?接雨水
這道題就是要求解每一個柱子左邊第一個比它高的柱子，以及右邊第一個比它高的柱子，然后這兩個柱子間形成的凹槽面積。
注意，是橫向掃來求面積。比如下圖，4號柱左邊第一個比它高的柱子是3號，右邊第一個比它高的是7號，面積是藍色框（遍歷到7號柱時才會計算面積）。
我們額外用一個棧來存儲左邊第一個更高柱子的編號（為什么是左邊，因為用for循環(huán)遍歷是從左邊開始的，左邊代表遍歷過了的信息）。
右邊第一個更高的柱子會出現(xiàn)在for循環(huán)遍歷時，見下面的case 3。
?在用for循環(huán)遍歷每一跟柱子時，會出現(xiàn)以下三種情況，我們要根據(jù)不同情況來選擇如何操作棧。
- case 1：當(dāng)前遍歷的元素（柱子）高度小于棧頂元素的高度 height[i] < height[st.top()]
- case 2：當(dāng)前遍歷的元素（柱子）高度等于棧頂元素的高度 height[i] == height[st.top()]
- case 3：當(dāng)前遍歷的元素（柱子）高度大于棧頂元素的高度 height[i] > height[st.top()]? ?（碰到了右邊第一個更高的柱子）
?
int trap(vector<int> &height) { int ans{0}; stack<int> stk; // 單調(diào)遞增棧 for (int i = 0; i < height.size(); ++i) { while (!stk.empty() && height[i] > height[stk.top()]) // case 3 { int right = i; int mid = stk.top(); stk.pop(); if (!stk.empty()) { int left = stk.top(); // 彈出mid后，棧頂元素就是mid左側(cè)第一個比它高的柱子 // 計算面積 int width = right - left - 1; int h = min(height[left], height[right]) - height[mid]; ans += width * h; } } // case 1&2 stk.push(i); } return ans; }
?
84.?柱狀圖中最大的矩形
42. 接雨水?是找每個柱子左右兩邊第一個大于該柱子高度的柱子，而本題是找每個柱子左右兩邊第一個小于該柱子的柱子。
因此與接雨水相反，該題使用單調(diào)遞增棧。
如下圖，在2號柱（value: 5）柱左邊第一個更小的柱子是1號柱（value: 1），右邊第一個更小的柱子是4號柱（value: 2）。意味著以5為高度能貫穿兩個邊界這之間的柱子。
?
int largestRectangleArea(vector<int> &heights) { stack<int> stk; // 單調(diào)遞減棧 int ans{0}; heights.insert(heights.begin(), 0); // 數(shù)組頭部加入元素0 heights.push_back(0); // 數(shù)組尾部加入元素0 for (int i = 0; i < heights.size(); ++i) { while (!stk.empty() && heights[i] < heights[stk.top()]) { int right = i; int mid = stk.top(); stk.pop(); int left = stk.top(); int width = right - left - 1; int h = heights[mid]; ans = max(ans, width * h); } stk.push(i); } return ans; }
?文章來源地址http://www.zghlxwxcb.cn/news/detail-691870.html
到了這里，關(guān)于吃透單調(diào)棧（2）——解兩道Hard題：接雨水、柱狀圖中最大的矩形問題的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
