强化三 heap
2018-12-20 本文已影响0人
谢谢水果
42 Trapping Rain Water
- two pass 从左到右 找到每个元素左边最大值； 从右到左找到每个元素右边最大值；两个最大值中小的如果比当前元素大 说明有存水 累加
- one pass 左右相向双指针 每次小的移动 直到遇到大于当前值的 从新判断左右指针大小值
407 Trapping Rain Water II
- 考虑到上面的思路 先把外围边界入最小堆 每次挑出堆顶并向四周延伸
295 Find Median from Data Stream
480 Sliding Window Median
- 注意从哪一个堆里删除元素 同时删除之后为了保证minheap中元素个数等于或多一个 要调整两个堆的堆顶元素
42 Trapping Rain Water
class Solution {
//当前高度 当前位置左边最高和右边最高的最小值
public int trap(int[] height) {
return onePass(height);
// return twoPass(height);
}
public int twoPass(int[] height){
int result = 0;
if(height==null || height.length<=2)
return result;
int[] maxs = new int[height.length];
int leftmax = -1;
for(int i=0; i<height.length; i++){
maxs[i] = leftmax;
leftmax = Math.max(leftmax, height[i]);
}
int rightmax = -1;
for(int i=height.length-1; i>=0; i--){
maxs[i] = Math.min(maxs[i], rightmax);
if(maxs[i]>height[i])
result = result + maxs[i] - height[i];
rightmax = Math.max(rightmax, height[i]);
}
return result;
}
public int onePass(int[] height) {
if(height==null || height.length<=2)
return 0;
int result = 0;
int left = 0;
int right = height.length-1;
while(left<right){
int lower = Math.min(height[left],height[right]);
if(height[left]==lower){
left++;
while(left<right && height[left]<=lower){
result = result+lower-height[left];
left++;
}
}else{
right--;
while(left<right && height[right]<=lower){
result = result+lower-height[right];
right--;
}
}
}
return result;
}
}
407 Trapping Rain Water II
class Solution {
class Cell{
int x, y, h;
Cell(int x, int y, int h){
this.x = x;
this.y = y;
this.h = h;
}
}
public int trapRainWater(int[][] heightMap) {
int result = 0;
if(heightMap==null || heightMap.length==0 || heightMap[0]==null || heightMap[0].length==0)
return result;
boolean[][] visited = new boolean[heightMap.length][heightMap[0].length];
Comparator<Cell> com = new Comparator<Cell>(){
public int compare(Cell a, Cell b){
return a.h - b.h;
}
};
int[] dirx = {1, -1, 0, 0};
int[] diry = {0, 0, 1, -1};
Queue<Cell> queue = new PriorityQueue<Cell>(com);
init(visited, heightMap, queue);
while(!queue.isEmpty()){
Cell cell = queue.poll();
for(int i=0; i<4; i++){
int x = cell.x+dirx[i];
int y = cell.y+diry[i];
if(valid(x, y, visited)){
visited[x][y] = true;
queue.offer(new Cell(x, y, Math.max(heightMap[x][y], cell.h)));
if(cell.h>heightMap[x][y])
result = result + cell.h-heightMap[x][y];
}
}
}
return result;
}
private boolean valid(int x, int y, boolean[][] visited){
return x>=0 && x<visited.length && y>=0 && y<visited[0].length && visited[x][y] == false;
}
private void init(boolean[][] visited, int[][] heightMap, Queue<Cell> queue){
for(int i=0; i<heightMap.length; i++){
Cell cell1 = new Cell(i, 0, heightMap[i][0]);
visited[i][0] = true;
Cell cell2 = new Cell(i, heightMap[0].length-1, heightMap[i][heightMap[0].length-1]);
visited[i][heightMap[0].length-1] = true;
queue.offer(cell1);
queue.offer(cell2);
}
for(int i=0; i<heightMap[0].length; i++){
Cell cell1 = new Cell(0, i, heightMap[0][i]);
visited[0][i] = true;
Cell cell2 = new Cell(heightMap.length-1, i, heightMap[heightMap.length-1][i]);
visited[heightMap.length-1][i] = true;
queue.offer(cell1);
queue.offer(cell2);
}
}
}
295 Find Median from Data Stream
class MedianFinder {
Queue<Integer> minHeap;
Queue<Integer> maxHeap;
/** initialize your data structure here. */
public MedianFinder() {
minHeap = new PriorityQueue<Integer>();
maxHeap = new PriorityQueue<Integer>(Collections.reverseOrder());
}
public void addNum(int num) {
maxHeap.offer(num);
minHeap.offer(maxHeap.poll());
if(maxHeap.size()+2==minHeap.size()){
maxHeap.offer(minHeap.poll());
}
}
public double findMedian() {
if(minHeap.size()==maxHeap.size()){
return (double)(minHeap.peek()+maxHeap.peek())/2;
}
return minHeap.peek();
}
}
/**
* Your MedianFinder object will be instantiated and called as such:
* MedianFinder obj = new MedianFinder();
* obj.addNum(num);
* double param_2 = obj.findMedian();
*/
480 Sliding Window Median
class Solution {
public double[] medianSlidingWindow(int[] nums, int k) {
// write your code here
if(nums==null || k<=0 || nums.length<k)
return null;
double[] result = new double[nums.length-k+1];
Queue<Integer> minHeap = new PriorityQueue<Integer>();
Queue<Integer> maxHeap = new PriorityQueue<Integer>(Collections.reverseOrder());
for(int i=0; i<nums.length; i++){
maxHeap.offer(nums[i]);
minHeap.offer(maxHeap.poll());
if(minHeap.size()==maxHeap.size()+2)
maxHeap.offer(minHeap.poll());
if(i>=k-1){
if(minHeap.size()==maxHeap.size())
result[i-k+1] =((double)maxHeap.peek()+ (double)minHeap.peek())/2;
else
result[i-k+1] = (minHeap.peek());
if(minHeap.peek() <= nums[i-k+1]){
minHeap.remove(nums[i-k+1]);
}else{
maxHeap.remove(nums[i-k+1]);
}
if(maxHeap.size()>minHeap.size()){
minHeap.offer(maxHeap.poll());
}
if(minHeap.size()==maxHeap.size()+2)
maxHeap.offer(minHeap.poll());
}
}
return result;
}
}
