先用leetcode专题进行练习.
队列实现
622. 设计循环队列
利用循环队列节省空间, 可以复用申请的空间.
class MyCircularQueue {
private int[] queue;
private int capacity;
private int head;
private int count;
public MyCircularQueue(int k) {
queue = new int[k];
capacity = k;
head = 0;
count = 0;
}
public boolean enQueue(int value) {
if (count == capacity) return false;
queue[(head + count) % capacity] = value;
count += 1;
return true;
}
public boolean deQueue() {
if (count == 0) return false;
head = (head + 1) % capacity;
count -= 1;
return true;
}
public int Front() {
if (count == 0) return -1;
return queue[head];
}
public int Rear() {
if (count == 0) return -1;
return queue[(head + count - 1) % capacity];
}
public boolean isEmpty() {
return (count == 0);
}
public boolean isFull() {
return (count == capacity);
}
}
单调栈
496. 下一个更大元素I
题目给了两个数组, 实际上是简化了题目的思路, 让我们可以正向的把元素放进单调栈, 然后再把结果读出来. 实际上就算只有一个数组, 也能通过倒序把元素放进单调栈, 一次就读出结果.
class Solution {
public int[] nextGreaterElement(int[] nums1, int[] nums2) {
Map<Integer, Integer> map = new HashMap<>();
Deque<Integer> stack = new LinkedList<>();
for (int i = nums2.length - 1; i >= 0; i--) {
while (!stack.isEmpty() && stack.peek() <= nums2[i]) {
stack.pop();
}
if (stack.isEmpty()) map.put(nums2[i], -1);
else map.put(nums2[i], stack.peek());
stack.push(nums2[i]);
}
int[] res = new int[nums1.length];
for (int i = 0; i < nums1.length; i++) {
res[i] = map.get(nums1[i]);
}
return res;
}
}
503.下一个更大元素II
让数组长度翻倍即可, 相当于环形数组, 其他操作不变.
class Solution {
public int[] nextGreaterElements(int[] nums) {
int[] res = new int[nums.length];
Deque<Integer> stack = new LinkedList<>();
for (int i = 2 * (nums.length - 1); i >= 0; i--) {
while (!stack.isEmpty() && stack.peek() <= nums[i % nums.length]) stack.pop();
res[i % nums.length] = stack.isEmpty() ? -1 : stack.peek();
stack.push(nums[i % nums.length]);
}
return res;
}
}
参考
comments powered by Disqus