当前位置：首页 > ai >正文

Day05 单调栈 | 84. 柱状图中最大的矩形、42. 接雨水

ai 2025/9/7 9:52:10

一、84. 柱状图中最大的矩形

1、思路

单调递增，遇到低的矩形时，单调性破坏后，需要将栈里面的数据逐个出栈，宽度累加，然后计算面积,取最大值

2、代码

;
class Solution {public int largestRectangleArea(int[] heights) {// 单调递增，当单调性破坏后，需要将栈里面的数据逐个出栈，然后计算面积,取最大值// 2 入栈// 2 比 1 大，破坏单调递增，计算结果，出栈,栈空// 1入栈 5 入栈 6 入栈// 6比 2 大，破坏单调递增.计算结果出栈，结果比较大小,取大, 6出栈，宽度+1 , 5一样，依次出栈，宽度累加，取最大值,宽度+1// 1 比2 小 2入栈 ，同理，2 比 3小 ,3 入栈// 最后如果栈不为空,则计算栈里面面积最大数据Stack<Rect> stack = new Stack();int maxResult = 0;for (int h : heights) {int widthSum = 0;// 栈不为空并且栈顶（之前）高度大于等于当前高度，则计算栈里面面积最大数据while (!stack.empty() && stack.peek().getHeight() >= h) {Rect r = stack.pop();int a = r.getHeight(); // 栈顶高度widthSum += r.getWidth(); // 栈顶宽度 累加maxResult = Math.max(a * widthSum, maxResult);}Rect rect = new Rect(widthSum + 1, h);stack.push(rect);}int widthSum = 0;// 栈不为空，则计算栈里面面积最大数据while (!stack.empty()) {Rect r = stack.pop();int a = r.getHeight(); // 栈顶高度widthSum += r.getWidth(); // 栈顶宽度 累加maxResult = Math.max(a * widthSum, maxResult);}return maxResult;}
}class Rect {int width;int height;public Rect() {}public Rect(int width, int height) {this.width = width;this.height = height;}public int getWidth() {return width;}public int getHeight() {return height;}
}

二、42. 接雨水

1、思路

单调递减，遇到高的停止, 单调性破坏后，需要将栈里面的数据逐个出栈，宽度累加，然后计算面积,面积累加，注意边界，水流出

2、代码

class Solution {public int trap(int[] height) {// 单调递减，遇到高的停止,计算栈里面面积,累加宽度，出栈//2 1 0 1int maxResult = 0;Stack<Rect> stack = new Stack();for (int h : height) {int widthSum = 0;while (!stack.empty() && stack.peek().getHeight() < h) {Rect r = stack.pop();int width = r.getWidth();int h2 = r.getHeight();// 计算面积,宽度累加widthSum += width;// 如果弹一个后，栈为空，则水从左边流走了if(stack.empty()){continue;}maxResult += widthSum*(Math.min(h,stack.peek().getHeight()) - h2);}Rect rect = new Rect(widthSum + 1, h);stack.push(rect);}return maxResult;}}class Rect {int width;int height;public Rect() {}public Rect(int width, int height) {this.width = width;this.height = height;}public int getWidth() {return width;}public int getHeight() {return height;}
}