注册公司去哪个网站,中国建设银行网站运营模式,石家庄网站建设推广公司报价,天津建设信息工程42. 接雨水
暴力法
for循环遍历每一个柱子#xff0c;内层for循环找到左边和右边比它高的柱子 时间复杂度 n^2
优化#xff1a;添加一个预处理 定义一个数组#xff0c;存放该柱子右边比他高的柱子是哪一个 再用一个数组#xff0c;存放该柱子左边比他高的柱子是哪一个 …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 heightStackInteger stack new StackInteger();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;}StackInteger st new Stack(); //存的是下标st.push(0);int sum 0;for(int i1; iheight.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 i1; ilen; i) {maxLeft[i] Math.max(height[i], maxLeft[i-1]);}maxRight[len-1] height[len-1];for(int ilen-2; i0; i--) {// maxLeft[i] Math.max(height[i], maxLeft[i-1]);maxRight[i] Math.max(height[i],maxRight[i1]);}int sum 0;for(int i0; ilen; i) {int h Math.min(maxLeft[i],maxRight[i]) - height[i];if(h0) sumh; // h*1}return sum;}
}84.柱状图中最大的矩形 emmm 和接雨水到底哪里一样了 暴力法 双指针
遍历每一根柱子向左向右找比它小的边界算出面积并求最大 优化两个数组一个存放i左边比他矮的一个存放i右边
单调栈
写法不一样了栈中元素 从栈顶到栈底要 从大到小。
遍历一次就能处理完当前遍历的元素比栈口元素小的时候说明栈口柱子右边比它小的那个柱子找到了它左边比它小的柱子怎么找在栈中。
首尾补0 尾补0[2468] 首补0[8642]
class Solution {public int largestRectangleArea(int[] heights) {int[]newHeight new int[heights.length2];for(int i1; iheights.length; i) {newHeight[i] heights[i-1];}heights newHeight; //重定向StackInteger st new StackInteger();st.push(0);int res0;for(int i1; iheights.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;}
}单调栈最核心的其实是栈顶元素
