Ryan
BAN USER<pre lang="java" line="1" title="CodeMonkey634" class="run-this">public class MinStack<T extends Comparable<T>>
{
private Node<T>[] table;
private int size;
public T pop() {
if (this.isEmpty()) {
return null;
}
return table[--size].item;
}
public T min() {
if (this.isEmpty()) {
return null;
}
return table[--size].min;
}
public void push(T item) {
if (size == table.length) {
this.resize();
}
if (this.isEmpty()) {
table[size++] = new Node(item, item);
} else {
Node<T> top = table[size - 1];
T min = top.min.compareTo(item) < 0 ?
top.min : item;
table[size++] = new Node(item, min);
}
}
public boolean isEmpty() {
return this.size == 0;
}
private void resize() {
int newCapacity = 2 * this.table.length;
if (newCapacit < 0)
newCapacity = Integer.MAX_VALUE;
Node<T> newTable = (Node<T>) new Node[newCapacity];
System.arraycopy(table, newTable, size);
this.table = newTable;
}
private static class Node<T>
{
public final T item;
public final T min;
public Node(T item, T min) {
this.item = item;
this.min = min;
}
}
} </pre>
We can do a round of pre-processing on all links. Compute the coordinates of each link.
- Ryan August 16, 2010Then the question becomes: given a list of dots, find the nearest dot next to (x, y).
This becomes a "Nearest neighbor search" problem. Using a space partition method can solve the problem in O(logn).