什么网站上面能接点小活做网站建设方案硬件支撑

什么网站上面能接点小活做,网站建设方案硬件支撑,手机网站分辨率做多大,杭州网站制作 乐云践新思路#xff1a;本题和接雨水是遥相呼应的题目。原理上有很多相同的地方#xff0c;但细节上又有差异#xff0c;可以加深对单调栈的理解。#xff08;一#xff09;方法一#xff1a;暴力解法#xff0c;超时。#xff08;二#xff09;方法二#xff1a;双指针解法…思路本题和接雨水是遥相呼应的题目。原理上有很多相同的地方但细节上又有差异可以加深对单调栈的理解。一方法一暴力解法超时。二方法二双指针解法。本题要记录每个柱子左边第一个小于该柱子的下标而不是左边第一个小于该柱子的高度因此需要使用while循环查找。附代码class Solution { public int largestRectangleArea(int[] heights) { int len heights.length; int[] minLeftIndex new int[len]; //记录每个柱子左边第一个比它矮的柱子下标 int[] minRightIndex new int[len]; //记录每个柱子右边第一个比它矮的柱子下标 //记录左边第一个小于该柱子的下标 minLeftIndex[0] -1; for(int i 1;i len;i){ int t i - 1; //这里不是用if而是不断向右寻找的过程 while(t 0 heights[t] heights[i]){ t minLeftIndex[t]; //跳跃式查找不是逐个比较。因为如果heights[t]比当前柱子高那么比heights[t]更高的左边柱子也肯定比当前柱子高。这保证了O(n)的时间复杂度。 } minLeftIndex[i] t; } //记录每个柱子右边第一个小于该柱子的下标 minRightIndex[len - 1] len; for(int i len - 2;i 0;i--){ int t i 1; while(t len heights[t] heights[i]){ t minRightIndex[t]; } minRightIndex[i] t; } //求和 int res 0; for(int i 0;i len;i){ int sum heights[i] * (minRightIndex[i] - minLeftIndex[i] - 1); res Math.max(res,sum); } return res; } }三方法三单调栈。1.本题和42.接雨水是遥相呼应的因为接雨水是找每个柱子左右两边第一个大于该柱子高度的柱子而本题是找每个柱子左右两边第一个小于该柱子的柱子。2.单调栈的顺序因为是找每个柱子左右两边第一个小于该柱子的柱子因此顺序为单调递减从栈头到栈底。举例如下图所示只有栈里是从大到小的顺序才能保证可以从栈顶元素找到左右两边第一个小于栈顶元素的柱子3.栈顶元素、栈顶的下一个元素以及要入栈的元素就组成了要求最大面积的高度和宽度。4.分析三种情况1情况一当前遍历的元素的heights[i]大于栈顶元素heights[stack.peek()]的情况。2情况二当前遍历的元素的heights[i]等于栈顶元素heights[stack.peek()]的情况。3情况三当前遍历的元素的heights[i]小于栈顶元素heights[stack.peek()]的情况。5.在heights数组开头和末尾都加了一个元素0。1末尾加0如果数组本身就是升序的例如[2,4,6,8]那么入栈之后都是单调递减一直没有走情况三计算结果的那一步所以最后输出的就是0如下图所示。而在结尾加上0就会让栈里的所有元素走到情况三的逻辑。2开头加0如果数组本身是降序的例如[8,6,4,2]在8入栈后6开始与8进行比较此时可以得到mid(8)、right(6)但是得不到left。这是因为栈将8弹出之后栈里就没有元素了为了避免空栈取值会直接跳过计算结果的逻辑。之后又将6加入栈此时8已经弹出了然后就是4与栈口元素6进行比较周而复始计算的最后结果res就是0如下图所示。3因此需要在heights数组前后各加一个元素0。附代码class Solution { public int largestRectangleArea(int[] heights) { LinkedListInteger stack new LinkedList(); //数组扩容在头和尾各加入一个元素 int[] newHeights new int[heights.length 2]; newHeights[0] 0; newHeights[newHeights.length - 1] 0; for(int i 0;i heights.length;i){ newHeights[i 1] heights[i]; } heights newHeights; stack.push(0); int res 0; // 第一个元素已经入栈从下标1开始 for(int i 1;i heights.length;i){ //heights[i]是和heights[stack.peek()]进行比较的stack.peek()是下标 if(heights[i] heights[stack.peek()]){ stack.push(i); }else if(heights[i] heights[stack.peek()]){ stack.pop(); stack.push(i); }else{ while(heights[i] heights[stack.peek()]){ int mid stack.peek(); stack.pop(); int left stack.peek(); int right i; //此时left是左边第一个比mid矮的元素right是右边第一个比mid矮的元素 //(left,right)左开右开区间内的柱子都 mid的高度 //计算(left,right)区间的宽度 int w right - left - 1; //(left,right)区间的高度就是最矮点的高度即mid的高度 int h heights[mid]; res Math.max(res,w * h); } stack.push(i); } } return res; } }单调栈精简版System.arraycopy()的用法System.arraycopy(Object src,int srcPos,Object dest,int destPos,int length)。1src源数组。2srcPos源数组要复制的起始位置。3dest目的数组。4destPos目的数组放置的起始位置。5length复制的长度。附代码class Solution { public int largestRectangleArea(int[] heights) { int[] newHeight new int[heights.length 2]; System.arraycopy(heights,0,newHeight,1,heights.length); //在数组前后各加一个0 newHeight[heights.length 1] 0; newHeight[0] 0; LinkedListInteger stack new LinkedList(); stack.push(0); int res 0; for(int i 1;i newHeight.length;i){ while(newHeight[i] newHeight[stack.peek()]){ int mid stack.pop(); int w i - stack.peek() - 1; int h newHeight[mid]; res Math.max(res,w * h); } stack.push(i); } return res; } }