学校网站模板 dedecms,惠州网站建设公司曾,flash网站建设技术,手机网站在后台怎么做编辑503.下一个更大元素ll
初始思路#xff1a;这样这道题就变成了一道很纯粹的单调栈问题#xff0c;因为只涉及了一个数组。但又因为这个数组是一个循环数组所以问题又变的有些复杂。
初始思路#xff1a;
在循环数组的问题中#xff0c;比较需要考虑的就是数组中最后一个…503.下一个更大元素ll
初始思路这样这道题就变成了一道很纯粹的单调栈问题因为只涉及了一个数组。但又因为这个数组是一个循环数组所以问题又变的有些复杂。
初始思路
在循环数组的问题中比较需要考虑的就是数组中最后一个数字出现在数组头部的问题所以考虑将创建一个新数组数组中的元素为原数组元素数组中最后一个数组前的元素然后使用基本单调栈的方法处理该问题。answer数组和原数组大小相同。
class Solution {public int[] nextGreaterElements(int[] nums) {int[] ans new int[nums.length];Arrays.fill(ans,-1);int[] newnums new int[2*nums.length-1];for(int i 0;inewnums.length;i){if(inums.length){newnums[i] nums[i];}else{newnums[i] nums[i-nums.length];}}StackInteger st new Stack();st.push(0);for(int i 1;inewnums.length;i){if(newnums[i]newnums[st.peek()]){st.push(i);}else{while(!st.isEmpty()newnums[i]newnums[st.peek()]){int pos st.peek()nums.length?st.peek():st.peek()-nums.length;ans[pos] newnums[i];st.pop();}st.push(i);}}return ans;}
}
题解复盘:
直接使用取余操作代替填充数组
class Solution {public int[] nextGreaterElements(int[] nums) {//边界判断if(nums null || nums.length 1) {return new int[]{-1};}int size nums.length;int[] result new int[size];//存放结果Arrays.fill(result,-1);//默认全部初始化为-1StackInteger st new Stack();//栈中存放的是nums中的元素下标for(int i 0; i 2*size; i) {while(!st.empty() nums[i % size] nums[st.peek()]) {result[st.peek()] nums[i % size];//更新resultst.pop();//弹出栈顶}st.push(i % size);}return result;}
} 42.接雨水
初始思路题解复盘
大概能理解雨水的数量是如何计算出来的但是找到一套通用的计算公式还是比较困难的。 单调栈是按照行方向来计算雨水的。
以下逻辑主要就是三种情况
情况一当前遍历的元素柱子高度小于栈顶元素的高度 height[i] height[st.top()]情况二当前遍历的元素柱子高度等于栈顶元素的高度 height[i] height[st.top()]情况三当前遍历的元素柱子高度大于栈顶元素的高度 height[i] height[st.top()]
先将下标0的柱子加入到栈中st.push(0);。 栈中存放我们遍历过的元素所以先将下标0加进来。
然后开始从下标1开始遍历所有的柱子for (int i 1; i height.size(); i)。
如果当前遍历的元素柱子高度小于等于栈顶元素的高度就把这个元素加入栈中因为栈里本来就要保持从小到大的顺序从栈头到栈底。
如果当前遍历的元素柱子高度大于栈顶元素的高度此时就出现凹槽了如图所示 取栈顶元素将栈顶元素弹出这个就是凹槽的底部也就是中间位置下标记为mid对应的高度为height[mid]就是图中的高度1。
此时的栈顶元素st.top()就是凹槽的左边位置下标为st.top()对应的高度为height[st.top()]就是图中的高度2。
当前遍历的元素i就是凹槽右边的位置下标为i对应的高度为height[i]就是图中的高度3。
此时大家应该可以发现其实就是栈顶和栈顶的下一个元素以及要入栈的元素三个元素来接水
那么雨水高度是 min(凹槽左边高度, 凹槽右边高度) - 凹槽底部高度代码为int h min(height[st.top()], height[i]) - height[mid];
雨水的宽度是 凹槽右边的下标 - 凹槽左边的下标 - 1因为只求中间宽度代码为int w i - st.top() - 1 ;
当前凹槽雨水的体积就是h * w。
class Solution {public int trap(int[] height) {StackInteger st new Stack();st.push(0);int res 0;int mid 0;int h 0;int weight 0;for( int i 1;iheight.length;i){if(height[i]height[st.peek()]){st.push(i);}else{while(!st.isEmpty()height[i]height[st.peek()]){mid height[st.pop()];if(!st.isEmpty()){h Math.min(height[i],height[st.peek()])-mid; weight i-st.peek()-1;res res h*weight;}}st.push(i);}}return res;}
} 84.柱状图中最大的矩形
同上如何在单调栈的规律中找到求最大矩形的计算规律是一个有点想不明白的问题。
初始思路题解复盘 只有栈里从大到小的顺序才能保证栈顶元素找到左右两边第一个小于栈顶元素的柱子。
所以本题单调栈的顺序正好与接雨水反过来。
此时大家应该可以发现其实就是栈顶和栈顶的下一个元素以及要入栈的三个元素组成了我们要求最大面积的高度和宽度理解如何由单调栈问题思考出计算最大面积的方式 int w right - left - 1;int h heights[mid];result max(result, w * h);
理解为什么在首尾均需要添加0元素。
如果数组本身就是升序的例如[2,4,6,8]那么入栈之后 都是单调递减一直都没有走 情况三 计算结果的哪一步所以最后输出的就是0了。 如图 那么结尾加一个0就会让栈里的所有元素走到情况三的逻辑。
开头为什么要加元素0
如果数组本身是降序的例如 [8,6,4,2]在 8 入栈后6 开始与8 进行比较此时我们得到 mid8rigt6但是得不到 left。
mid、leftright 都是对应版本一里的逻辑
因为 将 8 弹出之后栈里没有元素了那么为了避免空栈取值直接跳过了计算结果的逻辑。
之后又将6 加入栈此时8已经弹出了然后 就是 4 与 栈口元素 8 进行比较周而复始那么计算的最后结果resutl就是0。 如图所示 所以我们需要在 height数组前后各加一个元素0。
添加0元素部分代码 int[] newHeight new int[heights.length 2];System.arraycopy(heights, 0, newHeight, 1, heights.length);newHeight[heights.length1] 0;newHeight[0] 0;
System.arraycopy(int[] arr, int star,int[] arr2, int start2, length);
5个参数 第一个参数是要被复制的数组 第二个参数是被复制的数字开始复制的下标 第三个参数是目标数组也就是要把数据放进来的数组 第四个参数是从目标数据第几个下标开始放入数据 第五个参数表示从被复制的数组中拿几个数值放到目标数组中
class Solution {public int largestRectangleArea(int[] heights) {int[] newheights new int[heights.length2];System.arraycopy(heights,0,newheights,1,heights.length);newheights[0] 0;newheights[newheights.length-1] 0;StackInteger st new Stack();st.push(0);int res 0;for(int i 1;inewheights.length;i){if(newheights[i]newheights[st.peek()]){st.push(i);}else{while(!st.isEmpty()newheights[i]newheights[st.peek()]){int mid st.pop();int height newheights[mid];int weight i-st.peek()-1;res Math.max(res,height*weight);}st.push(i);}}return res;}
} 单调栈总结 单调栈问题入门找一个元素右边第一个比该元素大的值时考虑使用单调栈从栈顶到栈底如果是递增趋势加入的元素是比peek小的。找右边第一个元素比该元素值大时为相反情况。需要注意的是此处我们需要在栈中存放的数值是数组下标。 与上一题相同一些区别是因为无需考虑数组下标栈中可以直接存放元素因为数组之中没有重复元素所以可以在数组2中寻找完然后再用map对应到数组1中。 这个系列中最简单的一道循环的部份用取余处理。 接雨水横向求取面积找到左边比当前大的值右边比当前大的值height Math.min(左、右)-midweight 右下标-左下标-1 柱状图中最大的矩形找到左边比当前小的值和右边比当前小的值height mid weight就是右下标-左下标-1
后两道题的难点计算面积并且更新。
