欢迎来到尧图网

客户服务 关于我们

您的位置:首页 > 新闻 > 国际 > 单调栈② | Java | LeetCode 接雨水 最大的矩形

单调栈② | Java | LeetCode 接雨水 最大的矩形

2025/1/26 17:48:38 来源:https://blog.csdn.net/yavlgloss/article/details/140853498  浏览:    关键词:单调栈② | Java | LeetCode 接雨水 最大的矩形

42. 接雨水

暴力法

for循环遍历每一个柱子,内层for循环找到左边和右边比它高的柱子
时间复杂度 n^2

优化:添加一个预处理
定义一个数组,存放该柱子右边比他高的柱子是哪一个
再用一个数组,存放该柱子左边比他高的柱子是哪一个

单调栈

单调栈:在每日温度题目中,其要找到右边第一个比他大的温度;适配到本题,就是找到当前柱子左边&右边 第一个比它大的温度

遍历一次就能处理完:当前遍历的元素比栈口元素大的时候,说明栈口柱子右边比它大的那个柱子找到了,它左边比它大的柱子怎么找?在栈中。
在这里插入图片描述

class Solution {public int trap(int[] height){int size = height.length;if (size <= 2) return 0;// in the stack, we push the index of array// using height[] to access the real heightStack<Integer> stack = new Stack<Integer>();stack.push(0);int sum = 0;for (int index = 1; index < size; index++){int stackTop = stack.peek();if (height[index] < height[stackTop]){stack.push(index);}else if (height[index] == height[stackTop]){// 因为相等的相邻墙,左边一个是不可能存放雨水的,所以pop左边的index, push当前的indexstack.pop();stack.push(index);}else{//pop up all lower valueint heightAtIdx = height[index];while (!stack.isEmpty() && (heightAtIdx > height[stackTop])){int mid = stack.pop();if (!stack.isEmpty()){int left = stack.peek();int h = Math.min(height[left], height[index]) - height[mid];int w = index - left - 1;int hold = h * w;if (hold > 0) sum += hold; //加不加大于0都一样stackTop = stack.peek();}}stack.push(index);}}return sum;}
}
  • 自己再做了一遍
class Solution {public int trap(int[] height) {if(height.length <= 2) {return 0;}Stack<Integer> st = new Stack<>(); //存的是下标st.push(0);int sum = 0;for(int i=1; i<height.length; i++) {// i 下标  height[i]值// height[st.peek()]  height[st.pop()]if(height[i] < height[st.peek()]) {st.push(i);} else if(height[i] == height[st.peek()]) {st.pop();st.push(i); //虽然值是一样的,但下标不一样} else { //发现凹槽了// int stackTop = st.peek();int right = i; //凹槽右侧高度while(!st.empty() && height[right] > height[st.peek()]) {int mid = st.pop();//凹点if(!st.empty()) {int left = st.peek();int w = right-left-1;int h = Math.min(height[left], height[right]) - height[mid];int hold = h*w;sum += hold;}}st.push(i);//体积 = w * h }}return sum;}
}

双指针

与单调栈不同的是,双指针求体积求的是 竖向的体积

class Solution {public int trap(int[] height) {int len = height.length;if(len <= 2) return 0;int[]maxLeft = new int[len];int[]maxRight = new int[len];maxLeft[0] = height[0];for(int i=1; i<len; i++) {maxLeft[i] = Math.max(height[i], maxLeft[i-1]);}maxRight[len-1] = height[len-1];for(int i=len-2; i>=0; i--) {// maxLeft[i] = Math.max(height[i], maxLeft[i-1]);maxRight[i] = Math.max(height[i],maxRight[i+1]);}int sum = 0;for(int i=0; i<len; i++) {int h = Math.min(maxLeft[i],maxRight[i]) - height[i];if(h>0) sum+=h; // h*1}return sum;}
}

84.柱状图中最大的矩形

emmm 和接雨水到底哪里一样了???

暴力法 双指针

遍历每一根柱子,向左向右找比它小的边界,算出面积并求最大
优化:两个数组,一个存放i左边比他矮的,一个存放i右边

单调栈

写法不一样了,栈中元素 从栈顶到栈底要 从大到小。

遍历一次就能处理完:当前遍历的元素比栈口元素小的时候,说明栈口柱子右边比它小的那个柱子找到了,它左边比它小的柱子怎么找?在栈中。

  • 首尾补0
    尾补0:[2,4,6,8]
    首补0:[8,6,4,2]
class Solution {public int largestRectangleArea(int[] heights) {int[]newHeight = new int[heights.length+2];for(int i=1; i<=heights.length; i++) {newHeight[i] = heights[i-1];}heights = newHeight; //重定向Stack<Integer> st = new Stack<Integer>();st.push(0);int res=0;for(int i=1; i<heights.length; i++) {if(heights[i]>heights[st.peek()]) {st.push(i);} else if(heights[i] == heights[st.peek()]) {st.pop();st.push(i);} else {//栈可能为空吗?while(heights[i] < heights[st.peek()]) {int mid = st.peek();st.pop();int left = st.peek();int right = i;int w = right - left - 1;int h = heights[mid];res = Math.max(res, w * h);}st.push(i);}}return res;}
}

单调栈最核心的其实是栈顶元素

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com