单调栈力扣题（leetcode）
84. 柱状图中最大的矩形
难度：困难
相关标签：栈、数组、单调栈
题目：
给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。
求在该柱状图中，能够勾勒出来的矩形的最大面积。
示例 1:
输入：heights = [2,1,5,6,2,3]
输出：10
解释：最大的矩形为图中红色区域，面积为 10
示例 2:
输入：heights = [2,4]
输出：4
提示：
- \(1 <= heights.length <=10^5\)
- \(0 <= heights[i] <= 10^4\)
核心知识点：单调栈
- 单调栈的核心作用：找到每个元素左边 / 右边最近的更小（或更大）元素的下标
- 本题需解决：对每个柱子，找到其左侧最近的更矮柱子（left [i]）和右侧最近的更矮柱子（right [i]）
- 矩形面积计算：\(height[i] × (right[i] - left[i] - 1)\)（宽度为左右边界之间的距离）
解题思路
- 预处理 \(left\) 数组：\(left [i] = 左侧最近的更矮柱子下标（无则为 - 1）\)
- 预处理 \(right\)数组：\(right [i] = 右侧最近的更矮柱子下标（无则为 n）\)
- 遍历每个柱子，计算面积并更新最大值
代码：
class Solution
{
public:int largestRectangleArea(vector<int>& heights) {int n = heights.size();if (n == 0) return 0;vector<int> left(n, -1); // 左侧最近更矮柱子下标vector<int> right(n, n); // 右侧最近更矮柱子下标stack<int> st; // 存储下标，保持栈内下标对应的高度递增// 计算left数组for (int i = 0; i < n; ++i) {// 栈不为空且栈顶元素高度≥当前高度 → 弹出（无利用价值）while (!st.empty() && heights[st.top()] >= heights[i]) st.pop();if (st.empty()) left[i] = -1;else left[i] = st.top();st.push(i);}// 清空栈，计算right数组st = stack<int>(); // 无clear()，重新构造for (int i = n - 1; i >= 0; --i) {while (!st.empty() && heights[st.top()] >= heights[i]) st.pop();if (st.empty()) right[i] = n;else right[i] = st.top();st.push(i);}// 计算最大面积int max_area = 0;for (int i = 0; i < n; ++i) {int area = heights[i] * (right[i] - left[i] - 1);max_area = max(max_area, area);}return max_area;}
};
相似题目
最大矩形困难
好子数组的最大分数困难
85. 最大矩形
难度：困难
相关标签：栈、数组、动态规划、矩阵、单调栈
题目：
给定一个仅包含 0 和 1 、大小为 rows x cols 的二维二进制矩阵，找出只包含 1 的最大矩形，并返回其面积。
示例 1:
输入：matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]
输出：6
解释：最大矩形如上图所示。
示例 2:
输入：matrix = [["0"]]
输出：0
示例 3:
输入：matrix = [["1"]]
输出：1
提示：
- \(rows == matrix.length\)
- \(cols == matrix[0].length\)
- \(1 <= rows, cols <= 200\)
- \(matrix[i][j] 为 '0' 或 '1'\)
核心思路：转化为第 84 题
- 对每一行，构造 “柱状图”：每个位置的高度为当前行向上连续 1 的个数
- 例如上述矩阵第 3 行（下标 2）的柱状图高度为 [3,1,3,2,2]
- 问题转化为：对每一行的柱状图，求最大矩形面积（直接复用第 84 题的单调栈模板）
解题步骤
- 预处理高度数组：\(h [i][j] = 第 i 行第 j 列向上连续 1 的个数\)（\(h [i][j] = 0 if matrix [i][j] == '0' else h [i-1][j] + 1\)）
- 对每一行的 h 数组，调用第 84 题的函数计算最大面积
- 取所有行的最大面积作为答案
代码：
class Solution
{
public:int largestRectangleArea(vector<int>& heights) {int n = heights.size();if(n == 0) return 0;vector<int> left(n, -1);vector<int> right(n, n);stack<int> st;for(int i = 0; i < n; i++){while(!st.empty() && heights[st.top()] >= heights[i]) st.pop();if(st.empty()) left[i] = -1;else left[i] = st.top();st.push(i);}st = stack<int>();for(int i = n-1; i >= 0; i--){while(!st.empty() && heights[st.top()] >= heights[i]) st.pop();if(st.empty()) right[i] = n;else right[i] = st.top();st.push(i);}int max_area = 0;for(int i = 0; i < n; i++){int area = heights[i] * (right[i] - left[i] - 1);max_area = max(max_area, area);}return max_area;}int maximalRectangle(vector<vector<char>>& matrix) {if (matrix.empty() || matrix[0].empty()) return 0;int n = matrix.size(); // 行数int m = matrix[0].size(); // 列数vector<int> h(m, 0); // 当前行的柱状图高度int max_area = 0;for (int i = 0; i < n; ++i) {// 更新高度数组hfor (int j = 0; j < m; ++j) {if (matrix[i][j] == '1') h[j] += 1;else h[j] = 0; }// 计算当前行柱状图的最大面积max_area = max(max_area, largestRectangleArea(h));}return max_area;}
};
相似题目
柱状图中最大的矩形困难
最大正方形中等
查找最大元素不超过 K 的有序子矩阵困难
739. 每日温度
难度：中等
相关标签：栈、数组、单调栈
题目：
给定一个整数数组 temperatures ，表示每天的温度，返回一个数组 answer ，其中 answer[i] 是指对于第 i 天，下一个更高温度出现在几天后。如果气温在这之后都不会升高，请在该位置用 0 来代替。
示例 1:
输入：temperatures = [73,74,75,71,69,72,76,73]
输出：[1,1,4,2,1,1,0,0]
示例 2:
输入：temperatures = [30,40,50,60]
输出：[1,1,1,0]
示例 3:
输入：temperatures = [30,60,90]
输出：[1,1,0]
提示：
- \(1 <= temperatures.length <= 10^5\)
- \(30 <= temperatures[i] <= 100\)
代码：
class Solution
{
public:vector<int> dailyTemperatures(vector<int>& temperatures) {int n = temperatures.size(); // 温度数组长度vector<int> ans(n, 0); // 答案数组，初始化为0（没有更高温就是0）stack<int> st; // 单调栈：存储【下标】，保证栈内温度【单调递增】// 从右往左倒序遍历，找每个位置【右边第一个更大的温度】for(int i = n-1; i >= 0; i--){// 核心：维护单调递增栈// 如果栈顶温度 ≤ 当前温度 → 栈顶不可能是答案，直接弹出while(!st.empty() && temperatures[st.top()] <= temperatures[i]) st.pop();// 此时栈顶就是【右边第一个比当前温度高的下标】if(st.empty()) ans[i] = 0;// 栈空 → 右边没有更大温度，ans[i]保持0不变else ans[i] = st.top() - i;// 计算天数差：更大温度的下标 - 当前下标st.push(i);// 把当前下标入栈，成为左边元素的候选答案}return ans;}
};
相似题目
下一个更大元素 I简单
股票价格跨度中等