leetcode 435. Non-overlapping Intervals | 435. 无重叠区间（单调栈）-蒲公英云

leetcode 435. Non-overlapping Intervals | 435. 无重叠区间（单调栈）

我就是我 2022-09-04 02:55 264阅读 0赞

题目

https://leetcode.com/problems/non-overlapping-intervals/
在这里插入图片描述

题解

我一开始是没有 get 到这道题的精髓的。只是在想，用贪心法，当两个 (a,b) pair 重叠时，删除 b 较大的就可以了，直到遍历完整个数组。

开始时只是维护了双指针在数组中游荡，分别叫 slow 和 fast。如果删 slow，则 slow 回退；如果删 fast，则 fast 前进。后来发现，指针是不能够随意回退的，因为你不能保证前面一个位置的元素仍然存在，可能早已被删除了。

那么在 slow 回退的时候，怎么能找到前一个元素呢？一种方法是维护一个 alive 数组，这种方法太矬了。另一种方法就是维护一个栈。于是突然发现，这不就是一个单调栈吗。。只不过是数组中对角线的两个数字单调而已。

附上草稿记录无效思考过程。。

在这里插入图片描述

class Solution { 
    public int eraseOverlapIntervals(int[][] arr) { 
        int L = arr.length;
        Arrays.sort(arr, (o1, o2) -> { 
            if (o1[0] != o2[0]) return o1[0] - o2[0];
            else return o1[1] - o2[1];
        });
        // 居然是个单调栈？？？
        Stack<int[]> stack = new Stack<>();
        int i = 0;
        while (true) { 
            while (i < L && !stack.isEmpty() && stack.peek()[1] > arr[i][0]) { 
                if (stack.peek()[1] > arr[i][1]) {  // 删slow
                    stack.pop();
                } else {  // 删fast
                    i++;
                }
            }
            if (i >= L) break;
            stack.push(arr[i++]);
        }
        return L - stack.size();
    }
}