12.14 算法练习

1. 每日温度

算法思路

1. 单调栈的作用：记录我们遍历过的元素，与当前的元素方便对比，本质是以空间换时间；
2. 比较当前元素与栈顶元素的大小，当当前元素大于栈顶元素时，持续弹出栈顶元素下标，记录结果，并将当前元素下标加入到栈中；
3. 当前元素小于栈顶元素时，直接将栈顶元素下标加入到栈中。

注意点

当当前元素大于栈顶元素时，要弹出栈顶元素，若接下来的栈顶元素依然小于当前元素，要继续弹出。

代码

class Solution {public int[] dailyTemperatures(int[] temperatures) {int[] result = new int[temperatures.length];Stack<Integer> sk = new Stack<>();sk.push(0);for(int i = 1; i<temperatures.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);Map<Integer, Integer> map = new HashMap<>();Stack<Integer> sk = new Stack<>();sk.push(0);for(int i = 0; i<nums1.length; i++){map.put(nums1[i], i);}for(int i = 0; i<nums2.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);Stack<Integer> sk = new Stack<>();sk.push(0);for(int i = 1; i<2*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) {Stack<Integer> sk = new Stack<>();sk.push(0);int result = 0;for(int i = 1; i<height.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) {Stack<Integer> sk = new Stack<>();sk.push(0);int [] newHeights = new int[heights.length + 2];newHeights[0] = 0;for(int i = 0; i<heights.length; i++){newHeights[i+1] = heights[i];}newHeights[newHeights.length-1] = 0;int result = 0;for(int i = 0; i<newHeights.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;}
}