題目鏈接

84. 柱狀圖中最大的矩形

85. 最大矩形

題目描述-84

給定 n 個非負整數，用來表示柱狀圖中各個柱子的高度。每個柱子彼此相鄰，且寬度為 1 。

求在該柱狀圖中，能夠勾勒出來的矩形的最大面積。

樣例-84

輸入: [2,1,5,6,2,3]輸出: 10

題目描述-85

給定一個僅包含 0 和 1 的二維二進制矩陣，找出只包含 1 的最大矩形，并返回其面積。

樣例-85

輸入:
[
["1","0","1","0","0"],
["1","0","1","1","1"],
["1","1","1","1","1"],
["1","0","0","1","0"]
]
輸出: 6

本題是要找到兩側第一個比它小的數的位置：找到每個柱形條左邊和右邊最近的比自己低的矩形條，然后用寬度乘高度，得到一個備選答案。這是單調棧的典型場景。

單調棧的核心使用場景：攤銷O(1)地獲得所有位置上兩側第一個比它大/小的數的位置

單調棧其它題目列表：

907. 子數組的最小值之和

739. 每日溫度

42. 接雨水

456. 132模式

注：驗證前序遍歷序列是否為某個二叉搜索樹的問題，本質上也是 132 模式的問題，如果前序遍歷序列不含 231 模式的子序列，則它是二叉搜索樹，依然用單調棧解。力扣上也有對應題：255. 驗證前序遍歷序列二叉搜索樹

496. 下一個更大元素 I

1019. 鏈表中的下一個更大節點

算法：單調棧

維護一個單調不減的棧，保存當前枚舉元素 cur 左側小于等于 cur 的元素的下標，其中棧頂離cur 最近，它是 cur 左側第一個比它小的元素的位置。

枚舉數組所有下標 j，把所有大于 nums[j] 的棧頂都彈出，直到棧頂小于等于 nums[j]，然后將 j 壓入(所有下標都會壓入)，當前枚舉的 j 就處理完了。答案在出棧時更新，出棧元素為 cur

cur = st.top(); st.pop();

此時對于已經彈出的 cur，當前的棧頂是 cur 左側第一個小于等于 cur 的，nums[j] 是 cur 右側第一個大于 cur 的。cur 對應的矩形寬度為

w = j - st.top() - 1;

當棧頂有連續的幾個值相等的下標時，最后一個彈出的 cur 會把左側第一個小于 cur 的下標取到，先彈出的取到的不是左側第一個小于 cur 的，只是第一個小于等于 cur的，這在此題不影響，但如果要返回每個位置能取到的最大矩形，則需要額外處理先彈出的幾個下標。

棧底始終放一個 -1 處理 nums[j] 比棧里所有元素都小的情況。

每個元素都要進棧一次出棧一次，總時間復雜度 O(N)

對于第85題，M * N 的矩陣，一行一行地考慮，對于第 i 行，矩陣的第 0 到第 i 行可以視為一個直方圖，然后照搬 84 的做法求該直方圖上的最大矩形。一共有 M 個直方圖，總時間復雜度 O(MN)。

代碼-84(c++)

class Solution { public:int largestRectangleArea(vector<int>& heights) {if(heights.empty()) return 0;int n = heights.size();stack<int> st({-1});int result = 0;for(int i = 0; i < n; ++i){if(st.top() == -1 || heights[st.top()] <= heights[i])st.push(i);else{while(st.top() != -1 && heights[st.top()] > heights[i]){int index = st.top();st.pop();int w = i - st.top() - 1;int area = w * heights[index];result = max(result, area);}st.push(i);}}while(st.top() != -1){int index = st.top();st.pop();int w = n - st.top() - 1;int area = w * heights[index];result = max(result, area);}return result;} };

代碼-85(c++)

class Solution { public:int maximalRectangle(vector<vector<char>>& matrix) {if(matrix.empty()) return 0;int n = matrix.size(), m = matrix[0].size();vector<int> heights(m, 0);int result = 0;for(int i = 0; i < n; ++i){_get_geights(matrix, heights, i);int result_i = _max_rec_hist(heights);result = max(result, result_i);}return result;}private:void _get_geights(vector<vector<char> >& matrix, vector<int>& heights, int i){int m = matrix[0].size();for(int j = 0; j < m; ++j){int cnt = 0;int h = i;while(h >= 0 && matrix[h][j] == '1'){++cnt;--h;}heights[j] = cnt;}}int _max_rec_hist(vector<int>& heights){int m = heights.size();stack<int> st;st.push(-1);int result = 0;for(int j = 0; j < m; ++j){while(st.top() != -1 && heights[st.top()] > heights[j]){int h = heights[st.top()];st.pop();int l = st.top();int w = j - l - 1;result = max(result, h * w);}st.push(j);}while(st.top() != -1){int h = heights[st.top()];st.pop();int l = st.top();int w = m - l - 1;result = max(result, w * h);}return result;} };

總結

以上是生活随笔為你收集整理的单调不减序列查询第一个大于等于_[力扣84,85] 单调栈的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。