版权声明:本文为博主原创文章,未经博主允许不得转载。 https://cloud.tencent.com/developer/article/1434769
详细代码可以fork下Github上leetcode项目,不定期更新。
题目摘自leetcode:
一道单调队列的题,不过这道题让我加深了对单调队列的理解。
滑动窗口系列,对下标的删选非常严格,所以在用数据结构存储时,可以存储下标,这样就能做到下标和数的双重筛选。
题目意思是说,让我们在滑动窗口滑动时,找到该区域内的最大值。这个问题换个角度思考或许更容易理解:
遍历当前元素i时,寻找前k个元素(包含i)这个范围内的最大值。
问题一旦被转换,这题似乎就没那么难了,本题的关键在于状态记录,两个状态,【下标】和【元素的大小关系】。下标是用来筛选滑动窗口外的元素,元素的大小关系是用来时刻保持一个最大队列。
思路:
所以它的高效性体现在,在前一个滑动窗口移动时,就有一个队列维护了单调递减队列,如果遇到的下一个元素比队尾的元素小时,可以直接忽略。其次,维护的单调队列部分元素将是后续滑动窗口的解,非常关键。
代码如下:
public int[] maxSlidingWindow(int[] nums, int k) {
if (nums == null || k == 0) return new int[0];
int[] ans = new int[nums.length - k + 1];
Deque<Integer> queue = new ArrayDeque<>();
for (int i = 0, c = 0; i < nums.length; i++){
while (!queue.isEmpty() && queue.peek() < i - k + 1) queue.poll();
while (!queue.isEmpty() && nums[queue.peekLast()] <= nums[i]) queue.pollLast();
queue.offer(i);
if (i >= k -1) ans[c++] = nums[queue.peek()];
}
return ans;
}
这道题就是一道典型的堆问题,不难理解,思路相对简单。
把list列表全部用优先队列存储,那么队首的一定是最大的,一旦拿到队首,就可以对该list进行切割(指针移到下一结点),加入队列,继续。直到所有list的指针都移到末尾。
代码如下:
public ListNode mergeKLists(ListNode[] lists) {
if (lists.length == 0 || lists == null) return null;
PriorityQueue<ListNode> queue = new PriorityQueue<>(lists.length, (a,b) -> (a.val - b.val));
ListNode dummy = new ListNode(0);
ListNode tail = dummy;
for (ListNode list : lists){
queue.offer(list);
}
while (!queue.isEmpty()){
tail.next = queue.poll();
tail = tail.next;
if (tail != null){
queue.offer(tail);
}
}
return dummy.next;
}
这道题难在一些细节处理上,思路倒不难想到,我们只要抓住那些关键点的比较就好了。
思路:
首先那些关键点一定存在于左边或者右边上,关键就在于如何对关键点的height进行比较。
一些细节问题:
有序列表我用了两个优先队列来实现,所以代码如下:
private class Sky{
int l;
int r;
int h;
public Sky(int l, int r, int h){
this.l = l;
this.r = r;
this.h = h;
}
@Override
public String toString() {
StringBuilder sb = new StringBuilder();
sb.append("[" + l + ", " + r + ", " + h + "]");
return sb.toString();
}
}
public List<int[]> getSkyline(int[][] buildings) {
Sky[] skys = new Sky[buildings.length];
//注意它的排序原则
PriorityQueue<Sky> lq = new PriorityQueue<>((a,b) -> (a.l != b.l ? a.l - b.l : b.h - a.h));
//注意它的排序原则
PriorityQueue<Sky> rq = new PriorityQueue<>((a,b) -> (a.r != b.r ? a.r - b.r : a.h - b.h));
for (int i = 0; i < buildings.length; i++){
skys[i] = new Sky(buildings[i][0],buildings[i][1],buildings[i][2]);
lq.offer(skys[i]);
rq.offer(skys[i]);
}
//输出按高度最高的输出
PriorityQueue<Sky> hq = new PriorityQueue<>((a,b) -> (b.h - a.h));
List<int[]> ans = new ArrayList<int[]>();
while (!lq.isEmpty() && !rq.isEmpty()){
if (lq.peek().l < rq.peek().r){
hq.offer(lq.peek());
//关键点去重
if (ans.size() == 0 || ans.get(ans.size()-1)[1] != hq.peek().h)
ans.add(new int[]{lq.peek().l,hq.peek().h});
lq.poll();
}else if (lq.peek().l > rq.peek().r){
hq.remove(rq.peek());
int height = hq.isEmpty() ? 0 : hq.peek().h;
if (ans.size() == 0 || ans.get(ans.size()-1)[1] != height)
ans.add(new int[]{rq.peek().r, height});
rq.poll();
}else{
hq.offer(lq.peek());
hq.remove(rq.peek());
if (ans.size() == 0 || ans.get(ans.size()-1)[1] != hq.peek().h)
ans.add(new int[]{lq.peek().l,hq.peek().h});
lq.poll();
rq.poll();
}
}
while (!rq.isEmpty()){
hq.remove(rq.peek());
int height = hq.isEmpty() ? 0 : hq.peek().h;
if (ans.size() == 0 || ans.get(ans.size()-1)[1] != height)
ans.add(new int[]{rq.peek().r, height});
rq.poll();
}
return ans;
}
这是最直观的做法了,当然在论坛上有一种更简单的想法,的确很聪明。我这里没有区分左边和右边,所以分了两个优先队列来装。但更精简的做法,就是把左边和右边放在一个容器里,那如何区分它们呢?
答:用高度的正负来区分,因为我们只需要对左边和右边排序,且后续在放入优先队列时,这高度信息也没损失,这样就少了我归并的一部分代码了。
接着就是对这些边进行排序了,排序时,先对边进行排序,当边相同时,把大的放在前面,这样就去重了!而且左边的排序和右边的排序刚好相反,符合,之前我的两个优先队列的排序规则。
接下来就是扫描了,代码如下:
public List<int[]> getSkyline(int[][] buildings) {
List<int[]> ans = new ArrayList<>();
List<int[]> heights = new ArrayList<>();
for (int i = 0; i < buildings.length; i++){
heights.add(new int[]{buildings[i][0],-buildings[i][2]});
heights.add(new int[]{buildings[i][1], buildings[i][2]});
}
Collections.sort(heights, (a,b) -> (a[0] != b[0] ? a[0] - b[0] : a[1] - b[1]));
Queue<Integer> queue = new PriorityQueue<>((a,b) -> (b-a));
queue.offer(0);
for (int[] h : heights){
if (h[1] < 0){
queue.offer(-h[1]);
}else{
queue.remove(h[1]);
}
if (ans.size() == 0 || ans.get(ans.size()-1)[1] != queue.peek())
ans.add(new int[]{h[0],queue.peek()});
}
return ans;
}
这代码看上去就优雅多了,判断语句还不够好,学到了。先假设一个prev,然后求个curr,更新给ans,让prev = curr
,那么带入下一轮,就是上一轮的答案。
代码如下:
public List<int[]> getSkyline(int[][] buildings) {
List<int[]> ans = new ArrayList<>();
List<int[]> heights = new ArrayList<>();
for (int i = 0; i < buildings.length; i++){
heights.add(new int[]{buildings[i][0],-buildings[i][2]});
heights.add(new int[]{buildings[i][1], buildings[i][2]});
}
Collections.sort(heights, (a,b) -> (a[0] != b[0] ? a[0] - b[0] : a[1] - b[1]));
Queue<Integer> queue = new PriorityQueue<>((a,b) -> (b-a));
//初始化挺关键,可以省去不少代码
queue.offer(0);
int prev = 0;
for (int[] h : heights){
if (h[1] < 0){
queue.offer(-h[1]);
}else{
queue.remove(h[1]);
}
int curr = queue.peek();
if (curr != prev){
ans.add(new int[]{h[0],curr});
prev = curr;
}
}
return ans;
}
啊,这道题是理解堆和中位数的一道样题啊!如何想到正解:
所以这道题,对中位数理解到位,答案不难想。用堆去维护这种弱序结构简直再好不过了,而且堆的维护成本只有logn\log n,维护强序找中位数,呵呵,要O(n)O(n)。
所以关键是!
中位数的定义:比它小的个数和比它大的个数相等,是一种较弱的定义,没必要用较强的有序结构去解,时间复杂度自然就下去了。
所以我的代码无非就是维护两个堆的size关系,要么相等,要么右堆比左堆大1,代码如下:
public class MedianFinder {
Queue<Integer> lf;
Queue<Integer> rt;
int N = 0;
public MedianFinder() {
rt = new PriorityQueue<>((a,b) -> (a - b));
lf = new PriorityQueue<>((a,b) -> (b - a));
}
public void addNum(int num) {
if (N == 0) {
rt.offer(num);
N++;
return;
}
int right = rt.peek();
if (N % 2 == 0){
if (num >= right){
rt.offer(num);
}else{
lf.offer(num);
rt.offer(lf.poll());
}
N++;
}else{
if (num >= right){
lf.offer(rt.poll());
rt.offer(num);
}else{
lf.offer(num);
}
N++;
}
}
public double findMedian() {
return N % 2 == 0 ? (rt.peek() + lf.peek()) / 2.0 : rt.peek();
}
public static void main(String[] args) {
MedianFinder mf = new MedianFinder();
mf.addNum(1);
mf.addNum(2);
System.out.println(mf.findMedian());
mf.addNum(3);
System.out.println(mf.findMedian());
}
}
还有一种更简洁的代码,当然这是基于上述代码的一种优化,如果你脑子够聪明,能一眼看出来,我也是没话讲,具体如何优化,专门再讲吧,此文只关注思路来源。
代码如下:
public class MedianFinder {
Queue<Integer> lf;
Queue<Integer> rt;
int N = 0;
public MedianFinder() {
rt = new PriorityQueue<>((a,b) -> (a - b));
lf = new PriorityQueue<>((a,b) -> (b - a));
}
public void addNum(int num) {
lf.offer(num);
rt.offer(lf.poll());
if (lf.size() < rt.size()){
lf.offer(rt.poll());
}
N++;
}
public double findMedian() {
return N % 2 == 0 ? (rt.peek() + lf.peek()) / 2.0 : lf.peek();
}
}