wordpress链接速度慢,北京搜索引擎优化,东旭网站建设,做网站源代码1. 每日温度
算法思路
1. 单调栈的作用#xff1a;记录我们遍历过的元素#xff0c;与当前的元素方便对比#xff0c;本质是以空间换时间#xff1b;
2. 比较当前元素与栈顶元素的大小#xff0c;当当前元素大于栈顶元素时#xff0c;持续弹出栈顶元素下标#xff0c;…1. 每日温度
算法思路
1. 单调栈的作用记录我们遍历过的元素与当前的元素方便对比本质是以空间换时间
2. 比较当前元素与栈顶元素的大小当当前元素大于栈顶元素时持续弹出栈顶元素下标记录结果并将当前元素下标加入到栈中
3. 当前元素小于栈顶元素时直接将栈顶元素下标加入到栈中。注意点
当当前元素大于栈顶元素时要弹出栈顶元素若接下来的栈顶元素依然小于当前元素要继续弹出。代码
class Solution {public int[] dailyTemperatures(int[] temperatures) {int[] result new int[temperatures.length];StackInteger sk new Stack();sk.push(0);for(int i 1; itemperatures.length; i){if(temperatures[i] temperatures[sk.peek()]){sk.push(i);}else{while(!sk.isEmpty() temperatures[i] temperatures[sk.peek()]){int index sk.pop();result[index] i - index;}sk.push(i);}}return result;}
}2. 下一个更大元素 I
算法思路
1. 题目所述要在数组2中找到与数组1相同的元素并将数组2中第一个比这个元素大的元素返回到数组1所对应的下标说明值和索引之间需要一个映射关系加之数组中没有重复元素所以可以使用HashMap
2. 判断数组2中当前元素与栈顶元素的大小如果当前元素小于等于栈顶元素则将当前元素下标放入栈内
3. 若当前元素大于栈顶元素则判断该栈顶元素是否在数组1中存在若存在则取数组1索引加入结果集中再弹出该栈顶元素若不存在则直接弹出直到当前元素小于等于栈顶元素再将当前元素加入栈中。注意点
由于不存在result返回-1使用要将result数组初始化为全是-1的数组。代码
class Solution {public int[] nextGreaterElement(int[] nums1, int[] nums2) {int[] result new int[nums1.length];Arrays.fill(result, -1);MapInteger, Integer map new HashMap();StackInteger sk new Stack();sk.push(0);for(int i 0; inums1.length; i){map.put(nums1[i], i);}for(int i 0; inums2.length; i){if(nums2[i] nums2[sk.peek()]){sk.push(i);}else{while(!sk.isEmpty() nums2[i] nums2[sk.peek()]){if(map.containsKey(nums2[sk.peek()])){result[map.get(nums2[sk.peek()])] nums2[i];}sk.pop();} sk.push(i);}}return result;}
}3. 下一个更大元素II
算法思路
可以通过拼接两个一模一样的数组来模拟环形数组。注意点
代码
class Solution {public int[] nextGreaterElements(int[] nums) {int[] result new int[nums.length];Arrays.fill(result,-1);StackInteger sk new Stack();sk.push(0);for(int i 1; i2*nums.length; i){int index i % nums.length;if(nums[index] nums[sk.peek()]){sk.push(index);}else{while(!sk.isEmpty() nums[index] nums[sk.peek()]){result[sk.peek()] nums[index];sk.pop();}sk.push(index);}}return result;}
}4. 接雨水
算法思路
1. 做一个预处理找出当前柱子左边比其高的柱子和右边比其高的柱子可以通过单调递增栈来实现
2. 如果当前元素比栈顶元素大那么栈顶元素右边第一个比它大的元素就是当前元素栈顶元素右边的元素就是左边第一个比它大的元素
3. 用单调栈来求解实际是横向求解雨水体积。注意点
1. 用 left、right、mid来表示柱子思路清晰不容易弄混。代码
class Solution {public int trap(int[] height) {StackInteger sk new Stack();sk.push(0);int result 0;for(int i 1; iheight.length; i){if(height[i] height[sk.peek()]){sk.push(i);}else{while(!sk.isEmpty() height[i] height[sk.peek()]){int mid sk.pop();if(!sk.isEmpty()){int left sk.peek();int h Math.min(height[left], height[i]) - height[mid];int w i - left -1;result h*w;}}sk.push(i);}}return result;}
}5. 柱状图中最大的矩形
算法思路
1. 以某个高度为基准向左右找比它矮的柱子找到了就可以最多延伸到比它矮的那个位置形成矩形
2. 计算矩阵的宽就是可以延伸的距离比基准柱子矮的柱子不能延伸right - left - 1而矩阵的高是Height[i]
3. 和接雨水那道题最大的区别是这个数组的首尾需要加0。注意点
1. 在末尾的位置加一个0避免本身数组是单调递增的加入到栈内单调递减从而触发不到计算过程的情况
2. 在开头的位置加一个0避免本身数组是单调递减的加入到栈内单调递增刚开始就进入计算过程但是会出现左边没有值的情况因为算法要比较三个柱子
3. 很难建议二刷。代码
class Solution {public int largestRectangleArea(int[] heights) {StackInteger sk new Stack();sk.push(0);int [] newHeights new int[heights.length 2];newHeights[0] 0;for(int i 0; iheights.length; i){newHeights[i1] heights[i];}newHeights[newHeights.length-1] 0;int result 0;for(int i 0; inewHeights.length; i){if(newHeights[i] newHeights[sk.peek()]){sk.push(i);}else{while(!sk.isEmpty() newHeights[i] newHeights[sk.peek()]){int mid sk.pop();if(!sk.isEmpty()){int left sk.peek();int w i-left-1;result Math.max(result, w * newHeights[mid]);}}sk.push(i);}}return result;}
}
