解法一：哈希表
建立哈希表，判断重复和前缀
class Trie {
HashSet<String> set = new HashSet<>();
public Trie() {
}
public void insert(String word) {
set.add(word);
}
public boolean search(String word) {
return set.contains(word);
}
public boolean startsWith(String prefix) {
for (String s : set) {
if(s.startsWith(prefix)) return true;
}
return false;
}
}解法：单调栈
建立两个栈，分别存放下标和值
如果 all 为空或者 price 小于栈顶，入栈 ，返回 1
如果 price >= 栈顶，出栈，直到小于等于栈顶或栈为空，入栈，返回下标之差或下标的值
class StockSpanner {
public StockSpanner() {
}
// 初始化下标
int index = 0;
// 存放下标
Deque<Integer> deque = new LinkedList<>();
// 存放值
Deque<Integer> all = new LinkedList<>();
public int next(int price) {
// 如果 all 为空或者 price 小于栈顶，入栈 ，返回 1
if(all.isEmpty() || price < all.peek()) {
all.push(price);
deque.push(index++);
return 1;
}
// 如果 price >= 栈顶，出栈，直到小于等于栈顶，入栈，返回下标之差
else {
int res = 0;
int i = 0;
while (!all.isEmpty() && price >= all.peek()){
i = deque.pop();
all.pop();
}
res = deque.isEmpty() ? index + 1 : index - deque.peek();
all.push(price);
deque.push(index++);
return res;
}
}
}解题思路：
初始时，设置一个小根堆和一个 min 记录最小的数
调用 addBack(int num) 方法时，如果 num 比 min 小，并且 heap 中不包含它，则将它加入到 heap 中
调用 popSmallest() 方法时，如果 heap 中为空，返回 min++，若果不为空，返回 heap.popll()
class RecentCounter {
List<Integer> record = new ArrayList<>();
public RecentCounter() {
}
public int ping(int t) {
int res = 0;
record.add(t);
for (int i = record.size() - 1; i >= 0; i--) {
if(record.get(i) <= t && record.get(i) >= t - 3000) res++;
else return res;
}
return res;
}
}