题目链接42. 接雨水、解题思路双指针按列计算具体思路首先初始化两个与 height 长度一致的数组 maxleft 和 maxright maxleft[i] 表示第 i 个位置左侧的最大柱子高度 maxright[i] 表示第 i 个位置右侧的最大柱子高度先从左到右遍历填充 maxleft maxleft[0] 初始化为 height[0]后续每个位置取前一个位置的 maxleft 值和当前高度的最大值再从右到左遍历填充 maxrightmaxright[ height.size() - 1] 初始化为 height 最后一个元素后续每个位置取后一个位置的 maxright 值和当前高度的最大值最后遍历每个位置计算该位置能接的雨水量 min(maxleft[i]maxright[i]) - height[i]仅当结果为正数时累加到总水量 ans 中最终返回 ans 即为能接的雨水总量。具体代码class Solution { public: int trap(vectorint height) { vectorint maxleft(height.size(), 0); vectorint maxright(height.size(), 0); maxleft[0] height[0]; for (int i 1; i height.size(); i) maxleft[i] max(maxleft[i - 1], height[i]); maxright[height.size() - 1] height[height.size() - 1]; for (int i height.size() - 2; i 0; i--) maxright[i] max(maxright[i 1], height[i]); int ans 0; for (int i 0; i height.size(); i) { if (min(maxleft[i], maxright[i]) - height[i] 0) ans min(maxleft[i], maxright[i]) - height[i]; } return ans; } };时间复杂度On空间复杂度On解题思路单调栈按行计算具体思路首先初始化单调递减栈存储 height 的索引保证栈内索引对应柱子高度单调递减将第一个索引 0 压入栈初始化总接水量 ans 为 0遍历索引从 1 到 height 末尾若栈非空且当前柱子高度 height[i] 大于栈顶索引对应高度说明找到凹槽的右边界弹出栈顶索引作为凹槽底部 mid若弹出后栈为空无左边界无法接水则跳出循环否则计算该凹槽的有效接水高度 h(左边界 stack.top() 和右边界 i 对应高度的较小值 - 凹槽底部 mid 对应高度)、有效接水宽度 w(右边界索引 i - 左边界索引stack.top() - 1)将 h * w 累加到总水量 ans重复该循环直到栈为空或当前高度不大于栈顶索引对应高度再将当前索引 i 压入栈以维持栈的单调递减特性遍历完成后ans 即为能接的雨水总量。具体代码class Solution { public: int trap(vectorint height) { stackint stack; stack.push(0); int ans 0; for (int i 1; i height.size(); i) { while(!stack.empty() height[i] height[stack.top()]) { int mid stack.top(); stack.pop(); if (stack.empty()) break; int h min(height[stack.top()], height[i]) - height[mid]; int w i - stack.top() - 1; ans h * w; } stack.push(i); } return ans; } };时间复杂度On空间复杂度On题目链接84.柱状图中最大的矩形解题思路单调栈具体思路首先在 heights 数组头部插入 0、尾部追加 0确保所有柱子都能被触发计算对应的最大矩形无需单独处理栈空 / 遍历结束的边界情况初始化单调递增栈存储数组索引保证栈内索引对应柱子高度单调递增并将第一个索引 0 压入栈初始化最大面积 ans 为 0遍历索引 i 从 1 到处理后 heights 的末尾若当前柱子高度 heights[i] 小于栈顶索引对应高度说明找到栈顶索引柱子的右边界弹出栈顶索引作为矩形高度对应的 mid计算以 heights[mid] 为高的矩形面积(宽度为右边界索引 i - 左边界索引stack.top() - 1高度为 heights[mid]并更新 ans 为当前 ans 和该面积的最大值重复该循环直到当前高度不小于栈顶索引对应高度再将当前索引 i 压入栈以维持栈的单调递增特性遍历完成后 ans 即为柱状图中能勾勒出的最大矩形面积。具体代码class Solution { public: int largestRectangleArea(vectorint heights) { stackint stack; heights.insert(heights.begin(), 0); heights.push_back(0); int ans 0; stack.push(0); for (int i 1; i heights.size(); i) { while(heights[i] heights[stack.top()]) { int mid stack.top(); stack.pop(); ans max(ans, (i - stack.top() - 1) * heights[mid]); } stack.push(i); } return ans; } };时间复杂度On空间复杂度On